Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214

Название	Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214
Дата	06.04.2023
Размер	452.53 Kb.
Формат файла
Имя файла	LabJob23.docx
Тип	Отчет #1041909
страница	7 из 12

1 2 3 4 5 6 7 8 9 ... 12

Этап 2. Преобразование таблицы конфигураций в управляющую таблицу восходящего парсера

В результате построения таблицы конфигураций (табл. 5.4.) было выяснено, что автомат, реализующий восходящее восстановление дерева грамматического разбора предложений языка, порождаемого грамматикой G_a₁, должен иметь ровно 13 состояний (с номерами 0…12). Общее количество символов (как терминальных, так и нетерминальных) вместе с псевдотерминалом ► равно 10.

Таблица конфигураций преобразуется в управляющую таблицу путем выполнения следующей процедуры.

Шаг 1. Строится пустая заготовка управляющей таблицы автомата, содержащая 13 строк и 10 столбцов (не считая заголовочных). Строки и столбцы нумеруются начиная с нуля. Нетерминальные символы грамматики в произвольном порядке помещаются в заголовки столбцов начиная с нулевого. Затем в произвольном порядке формируются заголовки столбцов, соответствующих терминальным символам. Последняя колонка ставится в соответствие псевдотерминальному символу конца входной цепочки ►.

Шаг 2. Занесение знаков операций Stop, Shift и Go. Знак операции Stop заносится в клетку строки состояния 1, колонка которой озаглавлена псевдотерминалом ►. Это соответствует моменту окончания восстановления дерева разбора согласно конфигурации Z : S ▼►.

Просматриваются колонки Из и Через таблицы конфигураций (табл. ?). Для каждой непустой пары значений из этих колонок формируется знак операции Shift, если символ в колонке Через является терминальным, и знак операции Go – в противном случае. Номер состояния, взятый из первой колонки текущей строки таблицы конфигураций, является параметром знака операции. Построенный таким образом знак операции заносится в клетку управляющей таблицы, находящуюся на пересечении строки с номером, взятым из колонки Из, и столбца, озаглавленного символом из колонки Через.

Например, при просмотре первой строки таблицы конфигураций, соответствующей состоянию номер 1, будет образован один знак операции G1, который должен быть занесен в клетку строки номер 0 того столбца управляющей таблицы, который помечен символом S. При обработке первой строки состояния 3 таблицы конфигураций будут образованы три одинаковых знака операции S3, которые должны быть помещены в клетки столбца, помеченного нетерминалом V, находящиеся на его пересечении со строками 0, 4 и 7.

Шаг 3. Занесение знаков операций Reduce. Просматривается содержимое колонки Конфигурация в поисках такой конфигурации, в которой маркер находится после последнего символа правой части правила. Формируется знак операции Rk,n, где k – количество символов в правой части правила; n – номер столбца управляющей таблицы, помеченного нетерминалом из левой части этого правила.

Выполняется попытка занесения сформированного знака операции во все клетки той строки управляющей таблицы, которая имеет номер, взятый из первой колонки таблицы конфигураций. Знак операции свертки не заносится в клетки, столбцы которых помечены нетерминалами. Если клетка уже содержит знак операции Shift или Reduce, то фиксируется конфликт типа сдвиг/свертка или свертка/свертка соответственно. Вопрос о том, что делать при возникновении конфликтов, будет рассматриваться ниже.

Применение этой процедуры к ранее построенной нами таблице конфигураций (см. табл. 5.4.) позволит получить такую управляющую таблицу автомата (табл. 5.5.).

Таблица 5.5.

(

)

►

Stop

R1,0

R1,1

R1,2

G10

G11

S12

R3,0

R3,1

R3,2

В качестве примера выполнения шага 3 рассмотрим состояние номер 2, в наборе конфигураций которого имеется конфигурация S : T▼. Формируется знак операции R1,0, поскольку правая часть правила содержит один символ T, а нетерминалу S из левой части поставлен в соответствие столбец управляющей таблицы с номером 0. При занесении этого знака в строку номер 2 управляющей таблицы будет обнаружен конфликт типа сдвиг/свертка в клетке столбца, помеченного терминалом *. Возникновение конфликта легко объясняется наличием в наборе конфигураций состояния номер 2 конфигурации
T : T▼ * V.

В табл. 5.5. серым фоном отмечены две клетки, в которых при занесении знаков операций были зафиксированы конфликты типа сдвиг/свертка.

Возникновение конфликтов, казалось бы, свидетельствует о недетерминированности конечного автомата, т. е. о невозможности восстановления дерева разбора некоторых входных цепочек без возвратов к пересмотру ранее принятых решений. Знаки операций сдвига и свертки не могут быть помещены в одну клетку управляющей таблицы в силу противоположности смысла действий, выполняемых этими операциями. То же самое относится и к потенциально возможным конфликтам типа свертка/свертка.

В одной клетке управляющей таблицы может находиться только один знак операции. Поэтому необходимо выяснить, может ли каждый конфликт быть разрешен в пользу одного из знаков операций. Только тогда можно считать завершенным процесс преобразования грамматики в восходящий синтаксический акцептор. Для разрешения конфликтов, очевидно, необходимо исследовать свойства исходной грамматики и порождаемого ею языка.

Однако в действительности для многих грамматик, в том числе для рассматриваемой грамматики G_a₁, возникновение конфликтов обусловлено не их свойствами и даже не свойствами порождаемого языка, а всего только несовершенством способа занесения знаков операций свертки в управляющую таблицу, сформулированного в шаге 3 процедуры.

Предотвращение конфликтов путем использования множеств последователей нетерминальных символов

Недетерминированность автомата, обнаруженная при попытке занесения знака операции свертки R1,0 (или R3,0) в клетку состояния номер 2 (или 10), находящуюся на пересечении со столбцом, помеченным терминалом * и содержащую знак операции S8, следует понимать, как возможность реализации более чем одной истории работы, начиная с момента выполнения одной из этих двух конфликтующих операций.

Причина различий в поведении автоматов состоит в следующем. Выполнение операции свертки в состоянии 2 (или 10) при входном символе * эквивалентно преобразованию промежуточного уровня восстанавливаемого дерева разбора, имеющего вид

… S + T * …,

в цепочку вида

… S * …

В этой цепочке сразу после нетерминала S следует знак операции умножения *. Однако множество последователей нетерминала S содержит только символы +, ) и ►. Символа * в этом множестве нет.

Следовательно, в процессе восстановления дерева разбора выполнять любую операцию свертки имеет смысл только в том случае, если в текущем состоянии автомата его входным символом является элемент множества последователей нетерминала, образующегося в результате свертки.

Поэтому при построении управляющей таблицы автомата сформированные на шаге 3 знаки операций свертки следует заносить только в те клетки строки данного состояния, которые находятся на пересечении со столбцами, соответствующими терминальным символам множества последователей нетерминала из левой части правила.

Используя множества последователей нетерминалов, применим модифицированный шаг 3 процедуры преобразования таблицы конфигураций в управляющую таблицу автомата к грамматике G_a₁. Теперь не возникают ранее фиксировавшиеся конфликты типа сдвиг/свертка, и управляющая таблица автомата получает вид, показанный в табл. 5.6.

Теперь автомат является детерминированным.

Для грамматики G_a₁ при построении управляющей таблицы не возникали конфликты типа свертка/свертка. В том случае если набор конфигураций некоторого состояния содержит две или более конфигураций вида

N : ▼

M : ▼,

занесение знаков операций свертки без использования множеств последователей нетерминалов N и M приведет к возникновению конфликтов типа свертка/свертка в каждой клетке данного состояния.

Таблица 5.6.

(

)

►

Stop

R1,0

R1,1

R1,2

G10

G11

S12

R3,0

R3,1

R3,2

При использовании множеств последователей для занесения знаков операций свертки в таблицу возникновение конфликтов зависит от того, пересекаются ли M_посл(N) и M_посл(M). Если их пересечение пусто, то в данном состоянии конфликты типа свертка/свертка не возникнут.

Использование множеств последователей для занесения знаков операций свертки в управляющую таблицу восходящего синтаксического акцептора автоматически разрешает вопрос о возможности использования в грамматике правил вида N : ε.

Действительно, конфигурация вида N : ε ▼ (или эквивалентная ей N : ▼), требующая выполнения свертки пустой цепочки в нетерминал N, появляется в таблице конфигураций только для тех состояний, для которых это диктуется совокупностью всех правил грамматики. Знаки операций свертки по таким правилам появятся в управляющей таблице именно в этих состояниях и только в тех столбцах, которые помечены терминалами, принадлежащими множеству последователей N.

Отсутствие лишних знаков операции свертки в клетках столбцов управляющей таблицы, помеченных терминалами, не входящими в множества последователей соответствующих нетерминалов, обеспечивает более быстрое обнаружение ошибок в неправильных входных цепочках.

LR(0)- и SLR(1)-грамматики и автоматы

Если при преобразовании грамматики G в управляющую таблицу восходящего синтаксического акцептора не возникает ни одного конфликта типа сдвиг/свертка или свертка/свертка даже без использования множеств последователей нетерминальных символов для расстановки знаков операций свертки, то G называется LR(0)-грамматикой.

Здесь буква L является сокращением английского слова Left и означает, что входная цепочка символов обрабатывается слева направо. Буква R есть сокращение слова Right и означает, что история работы автомата отражает процесс восстановления так называемого обратного правого дерева грамматического разбора. Число в скобках обозначает наименьшую длину подцепочек входных символов, необходимых для разрешения или предотвращения всех конфликтов типа сдвиг/свертка или свертка/свертка.

Таблица 5.7.

Грамматика G_a₀
0	Z : S 
1	S : T
2	S : S + T
3	T : ( S )
4	T : ident
5	T : const

Обозначение LR(0)-грамматик свидетельствует о том, что при их использовании для построения управляющей таблицы восходящего синтаксического акцептора конфликтов не возникает вообще. Грамматики, относящиеся к классу LR(0), существуют, в чем можно убедиться при построении восходящего акцептора для системы порождающих правил, показанной в табл. 5.7.

Однако синтаксис типичных языков программирования не может быть определен LR(0)-грамматикой. Этот класс грамматик слишком узок и может представлять собой только теоретический интерес.

Если при преобразовании грамматики в управляющую таблицу восходящего синтаксического акцептора все конфликты типа сдвиг/свертка или свертка/свертка удается разрешить (или предупредить) с использованием множеств последователей нетерминальных символов, содержащих цепочки терминалов длины 1, то грамматика относится к классу SLR(1)-грамматик.

Буква S в этом обозначении означает сокращение английского слова Simple – простая.

Преобразование грамматики G_a₁ в управляющую таблицу восходящего акцептора потребовало, как мы убедились, использования множеств последователей нетерминалов, содержащих одиночные терминальные символы.

Поскольку при этом все конфликты были предупреждены, данная грамматика относится к классу SLR(1).

Для большинства современных языков программирования не существует порождающих грамматик класса SLR(1). Поэтому необходимо рассмотреть более широкий класс грамматик, на основе которых может быть организовано восходящее детерминированное восстановление дерева разбора.

Этот класс грамматик называют LR(1)-грамматиками.

Ожидаемый правый контекст и LR(1)-автоматы

Для разрешения конфликтов типа «сдвиг/свертка» и «свертка/свертка» при построении таблицы конфигураций нужно связать с каждой конфигурацией, требующей выполнения операции свертки, такие множества терминальных символов, которые могут действительно ожидаться на входе автомата после выполнения операции свертки. Очевидно, что эти множества должны быть подмножествами полного множества последователей для каждого нетерминала, находящегося в левой части любой такой конфигурации.

Определять такие множества придется для всех конфигураций в таблице. Это следует из того, что любое состояние восходящего акцептора определяется взаимосвязанным набором конфигураций, перечень которых зависит, во-первых, от того, как (из какого состояния и через какой символ) была сформирована база, а во-вторых, от того, каково множество конфигураций замыкания базы.

Множество символов, допустимых на входе автомата после выполнения операции свертки в любом состоянии (и, естественно, после операции Go, обрабатывающей нетерминал, полученный в результате этой свертки), в литературе принято называть ожидаемым правым контекстом. Конфигурацию, к которой приписан в точности один символ ожидаемого правого контекста, будем называть канонической расширенной конфигурацией:

N :  ▼ , { t }

Правила формирования ожидаемого правого контекста.

Ожидаемый правый контекст базовой конфигурации нулевого состояния состоит из псевдотерминального символа ► конца текста (файла). Действительно, если входное предложение является правильным и восходящему акцептору удалось свернуть его в начальный нетерминал грамматики, то после этой свертки на входе автомата никаких других символов быть не может.
Перенос маркера через любой символ (образование базы другого состояния, а при работе автомата – выполнение операции Shift или Go) порождает конфигурацию, правый контекст которой совпадает с правым контекстом исходной конфигурации. Действительно, если взять базовую конфигурацию нулевого состояния и перенести маркер через начальный нетерминал (выполнить операцию Go после свертки правильного предложения в начальный нетерминал грамматики), то на входе автомата должен появиться псевдотерминал конца текста.
Осталось выяснить, каким образом формируется ожидаемый правый контекст при выполнении замыкания базового набора конфигураций произвольного состояния. Суть процесса замыкания, как определялось в разделе 3.3.4 ранее, состоит в следующем.

Если имеется конфигурация вида N :  ▼ X  , то каждое правило для нетерминала X превращается в конфигурацию путем установки маркера перед первым символом правой части и добавляется к множеству конфигураций данного состояния, если ее в нем еще нет:

X : γ₁ → X : ▼ γ₁

X : γ₂ → X : ▼ γ₂

...

X : γ_n → X : ▼ γ_n

При построении таблицы канонических расширенных конфигураций с любой исходной конфигурацией N :  ▼ X  связан правый контекст, содержащий символ t₀, ожидаемый на входе автомата после свертки цепочки  X  в нетерминал N:

N :  ▼ X  , {t₀ }.

Очевидно, что после свертки любой из цепочек γ_i в нетерминал X на входе автомата ожидаются символы, входящие в множество предшественников цепочки , а если эта цепочка состоит только из аннулируемых нетерминалов или вообще пуста – еще и символ t₀. Таким образом, определение множества ожидаемых символов при замыкании любой конфигурации производится по формуле

M_опк(X : ▼γ_i) = M_пред(),

если  – цепочка, содержащая хотя бы один терминал или неаннулируемый нетерминал;

M_опк(X : ▼γ_i) = {t₀ },

если  – пустая цепочка;

M_опк(X : ▼γ_i) = M_пред() ⋃ {t₀ },

если  – цепочка, состоящая только из аннулируемых нетерминалов.

Получив множество символов ожидаемого правого контекста M_опк( ▼ X , {t₀ }) = { t₁, t₂ … t_k}, легко можно построить все дочерние по отношению к исходной канонические конфигурации:

M : ▼γ₁, { t₁}M : ▼γ₁, { t₂}…M : ▼γ₁ , { t_k}

M : ▼γ₂, { t₁}M : ▼γ₂ , { t₂}…M : ▼γ₂ , { t_k}

...

M : ▼γ_n, { t₁}M : ▼γ_n , { t₂}…M : ▼γ_n , { t_k}

Теперь окончательно сформулируем правила построения таблицы канонических конфигураций.

Базой нулевого состояния является конфигурация вида

Z : ▼S ► , {►},

где S – начальный нетерминал грамматики; ► – псевдотерминал «конец файла».

При формировании замыкания каждая вновь построенная каноническая конфигурация добавляется к множеству конфигураций данного состояния, если в этом множестве еще нет в точности такой конфигурации (с учетом ожидаемого правого контекста).
При формировании базы новое состояние образуется, если нет ни одного состояния с точно таким же базовым набором канонических конфигураций. Еще раз подчеркнем, что канонические конфигурации различаются, если их помеченные правила одинаковы, но различны символы ожидаемого правого контекста.

Грамматики, для которых детерминированный восходящий синтаксический акцептор может быть построен только с использованием канонических конфигураций, называются LR(1)-грамматиками.

Однако грамматика G_LR на самом деле относится к промежуточному между SLR(1)- и LR(1)- грамматиками классу грамматик – так называемым LALR(1)-грамматикам. Буквы LA в названии класса грамматик являются сокращением от английского термина «lookahead», который переводится как «предварительный просмотр». В данном случае речь идет о предварительном (выполняемом при построении управляющей таблицы автомата) просмотре множеств символов ожидаемого правого контекста для разрешения или предупреждения возможных конфликтов «сдвиг/свертка» и «свертка/свертка».

LALR(1)-грамматики и автоматы

Рассмотренный в предыдущем разделе метод построения восходящего синтаксического акцептора можно модифицировать, используя вместо канонических так называемые расширенные конфигурации. Расширенной называется конфигурация, с которой связано некоторое множество символов ожидаемого правого контекста:

N :  ▼  , {t₁, t₂, … t_k}.

В отличие от канонических две расширенные конфигурации, имеющие одинаковое маркированное правило и разные множества символов ожидаемого правого контекста, могут быть объединены в одну конфигурацию путем слияния ОПК:

N :  ▼  , {t₁} и N :  ▼  , {t₂} эквивалентны N :  ▼  , {t₁, t₂}.

Сформулируем две разных технологии построения таблицы расширенных конфигураций. Согласно одной технологии должно быть выполнено следующее. Строится таблица канонических конфигураций как в разделе 3.3.9.
Просматриваются множества конфигураций каждого состояния. Если в них обнаруживаются пары конфигураций с одинаковым маркированным правилом, то каждая такая пара заменяется одной расширенной конфигурацией с объединенным ожидаемым правым контекстом. Если одна из конфигураций пары являлась базовой, то базовой должна быть и конфигурация, полученная в результате объединения пары конфигураций. Если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее К_исх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т.е. таких, для которых К_исх является родительской либо при выполнении замыкании, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.
Просматриваются все возможные пары состояний. Если два состояния имеют одинаковые (по маркированным правилам) наборы базовых расширенных конфигураций, то эти состояния сливаются, ожидаемые правые контексты пар всех конфигураций с одинаковым маркированным правилом объединяются. При слиянии состояний одно из них удаляется, но в оставшемся состоянии должна быть сохранена информация о том, откуда образовалось удаляемое состояние, т. е. содержимое колонок «Из» и «Через». Затем, если изменилось множество символов ОПК какой-либо базовой конфигурации (обозначим ее К_исх), то пересчитываются ожидаемые правые контексты всех ее дочерних конфигураций, т. е. таких, для которых К_исх является родительской либо при выполнении замыкания, либо при образовании другой базы. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока фиксируются изменения ожидаемого правого контекста дочерних конфигураций.

Перед слиянием каждой пары состояний можно проверять, не приведет ли это слияние к конфликту, которого не было в исходной таблице канонических конфигураций. Просматриваются пересечения множеств символов ОПК всех возможных пар конфигураций, первая из которых принадлежит одному состоянию, а вторая – другому. Если пересечение не пусто, и конфигурации требуют свертки по разным правилам, то состояния слиянию не подлежат. Далее, если одна из конфигураций требует сдвига по терминалу, принадлежащему ожидаемому правому контексту другой конфигурации, то выполнять слияние состояний не следует.

Согласно такой технологии строятся восходящие синтаксические акцепторы в учебном пакете автоматизации проектирования трансляторов ВебTрансБилдер.

Вторая технология заключается в следующем:

Базой нулевого состояния является конфигурация вида

Z : ▼S ► , {►},

где S – начальный нетерминал грамматики; ► – псевдотерминал «конец файла».

При формировании замыкания каждая вновь построенная расширенная конфигурация добавляется к множеству конфигураций данного состояния, если в этом множестве еще нет конфигурации с точно таким же маркированным правилом. Если же в множестве конфигураций состояния уже есть конфигурация с точно таким же маркированным правилом (обозначим ее К_исх), то ее множество символов ожидаемого правого контекста объединяется с ОПК новой конфигурации. Если ожидаемый правый контекст конфигурации К_исх изменился в результате объединения, то пересчитываются ожидаемые правые контексты всех тех конфигураций, для которых конфигурация К_исх является родительской как при формировании новой базы, так и при замыкании множеств конфигураций. Процедура пересчета должна продолжаться рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.
При формировании базы новое состояние образуется, если нет ни одного состояния с точно таким же (по маркированным правилам) базовым набором расширенных конфигураций. Если же существует такое состояние то новое состояние не формируется. Вместо этого объединяются множества ОПК одинаковых по маркированным правилам базовых конфигураций. Если при этом изменился ожидаемый правый контекст какой-либо базовой конфигурации, то должны быть пересчитаны ОПК всех ее дочерних конфигураций. Процедуру пересчета следует продолжать рекурсивно до тех пор, пока не перестанут изменяться ожидаемые правые контексты дочерних конфигураций.

Обе технологии требуют выполнения большого объема вычислений при пересчете ожидаемых правых контекстов.

При использовании расширенных конфигураций для предупреждения конфликтов используется тот же самый способ формирования базовых конфигураций состояний автомата, что и в случае формирования таблицы простых конфигураций. Поэтому размеры управляющей таблицы для любой грамматики будут одинаковы как при использовании расширенных конфигураций, так и без вычисления ожидаемого правого контекста. Грамматики, для которых удается построить детерминированный восходящий синтаксический акцептор с использованием расширенных конфигураций, называются LALR(1)-грамматиками.

Класс LALR(1)-грамматик более широк, чем класс SLR(1), однако существуют языки (в том числе практически все известные языки программирования), для которых не может быть найдена порождающая LALR(1)-грамматика. В то же время доказано, что для любого детерминированного контекстно-свободного языка существует хотя бы одна порождающая LR(1)-грамматика. Тем не менее задача нахождения грамматики требуемого класса, даже если известно, что она должна существовать для данного языка, алгоритмически неразрешима.

Порядок выполнения работы (рекомендуется использовать в качестве примера систему правил Samples/Sample5):

Завершить разработку грамматику языка, заданного на курсовую работу. Грамматика должна определять программы, включающие несколько функций.
Используя пакет ВебТрансБилдер и полную грамматику своего языка:

построить табличную реализацию восходящего синтаксического анализатора, найти в программном коде парсера управляющую таблицу автомата, и его программную модель, описать в отчете эти фрагменты кода парсера;
построить процедурную реализацию восходящего синтаксического анализатора, сравнить текст построенного программного модуля с кодом табличного парсера, описать результаты сравнения в отчете;
изучить структуру таблицы канонических и таблицы расширенных конфигураций (пункты меню «Показать/Канонические конфигурации» и «Показать/Расширенные конфигурации»), описать на примерах операций Go, Shift и Reduce (по одной, взятой произвольным образом из управляющей таблицы) связь этих таблиц с управляющей таблицей восходящего парсера;
выявить конфликты типов «сдвиг–свертка» и «свертка–свертка», разрешенные и, возможно, не разрешенные преобразователем, описать способы разрешения конфликтов.

Выполнить трассировку процессов нисходящего синтаксического акцепта, включая флажок показа истории работы при запуске транслятора на тестирование. Изучить по историям работы поведение всех построенных синтаксических акцепторов при разборе как правильных предложений, так и предложений с намеренно внесенными синтаксическими ошибками. Описать фрагменты этих историй, включающие не менее, чем по одной операции Go, Shift и Reduce.
Проанализировать и сравнить между собой все полученные тексты программ и результаты выполнения пункта 4.2. Оценить степень пригодности изученных вариантов реализации нисходящих синтаксических акцепторов для выполнения курсовой работы. Отразить в заключении к отчету результат анализа и оценки.
Подготовить, сдать и защитить отчет к лабораторной работе.

Требования к содержанию отчета.

Отчет должен содержать:

цель работы;
фрагменты кода процедурной реализации восходящего и управляющей таблицы автоматной реализации восходящего синтаксического акцептора, описание структур данных и алгоритмов работы этих реализаций;
фрагменты историй работы процедурной и автоматной реализаций восходящего синтаксического акцептора для правильного и ошибочного тестовых примеров с объяснением принципов работы акцепторов;
выводы и заключение.

Контрольные вопросы

Что хранится в стеке восходящего парсера?
Что такое операция перехода восходящего парсера?
Если грамматика относится к классу SLR(1), то можно ли по ней построить нисходящий синтаксический акцептор?
Перечислите все знаки операций восходящего синтаксического акцептора, объясните назначение их полей (параметров).
Постройте историю работы восходящего синтаксического акцептора при разборе цепочки: (((x)))
Что такое конфигурация?
Напишите LR-грамматику для условного оператора С-подобного языка, имеющего и полную и сокращенную форму.
Какие грамматики относятся к классу LALR(1)?
Что такое конфликт «сдвиг/свертка»?
Как таблица конфигураций преобразуется в управляющую таблицу восходящего синтаксического акцептора?
Что такое ожидаемый правый контекст?
Что делает восходящий автомат при выполнении операции свертки?
Что такое детерминированное (безвозвратное) восстановление дерева грамматического разбора?
Как вычисляется ожидаемый правый контекст конфигурации?
Опишите технологию разработки процедурной реализации восходящего синтаксического акцептора.
Как выполняется операция сдвига?
Что такое LR(1)-грамматика?
Что такое конфликт «свертка/свертка»?
Перечислите все операции восходящего синтаксического акцептора.
Чем различаются понятия расширенной и канонической расширенной конфигурации?
Как используются множества последователей нетерминалов для предупреждения конфликтов при построении управляющей таблицы восходящего синтаксического акцептора по SLR(1)-грамматике?
Разработайте LR-грамматику для оператора переключателя (switch) С-подобного языка.

1 2 3 4 5 6 7 8 9 ... 12