LL парсер - LL parser

В Информатика, LL парсер (Слева направо, крайнее левое происхождение) - это нисходящий парсер для подмножества контекстно-свободные языки. Он анализирует ввод из Lвправо, выполняя Lсамый последний вывод предложения.

Парсер LL называется LL (k) парсер, если он использует k жетоны из смотреть вперед при разборе предложения. Грамматика называется LL (k) грамматика если LL (k) парсер может быть построен из него. Формальный язык называется LL (k) язык, если он имеет LL (k) грамматика. Набор LL (k) языков правильно содержится в языке LL (k+1) языков, для каждого k ≥ 0.^[1] Следствием этого является то, что не все контекстно-свободные языки могут быть распознаны LL (k) парсер.

LL-парсер называется LL-регулярным, если он анализирует в точности класс LL-регулярные языки^[2][3][4] Грамматики LLR являются правильным надмножеством грамматик LL (k) для любого k. Для каждой грамматики LLR существует анализатор LLR, который анализирует грамматику за линейное время.

Два номенклатурных типа анализатора выбросов - это LL (*) и LL (конечный). Парсер называется LL (*) / LL (конечный), если он использует стратегию синтаксического анализа LL (*) / LL (конечный). ^[5][6] Анализаторы LL (*) и LL (конечные) функционально более похожи на ПЭГ парсеры. Анализатор LL (конечный) может анализировать произвольную грамматику LL (k) оптимальным образом с точки зрения количества предварительных и предварительных сравнений. Класс грамматик, анализируемых стратегией LL (*), включает некоторые контекстно-зависимые языки из-за использования синтаксических и семантических предикатов и не был идентифицирован. Было высказано предположение, что парсеры LL (*) лучше рассматривать как TDPL парсеры.^[7]Вопреки распространенному заблуждению, парсеры LL (*) не являются LLR в целом, и конструкция гарантирует, что они будут работать хуже в среднем (суперлинейное по отношению к линейному времени) и намного хуже в худшем случае (экспоненциальное по отношению к линейному времени).

Грамматики LL, особенно грамматики LL (1), представляют большой практический интерес, поскольку синтаксические анализаторы для этих грамматик легко построить, а многие компьютерные языки по этой причине разработаны как LL (1).^[8] Парсеры LL - это парсеры на основе таблиц,^{[нужна цитата ]} похожий на Парсеры LR. Грамматики LL также могут быть проанализированы парсеры рекурсивного спуска. Согласно Уэйту и Гусу (1984),^[9] LL (k) грамматики были введены Стернсом и Льюисом (1969).^[10]

Обзор

Для данного контекстно-свободная грамматика, парсер пытается найти крайний левый вывод.Приведен пример грамматики. ${ displaystyle G}$:

1. ${ displaystyle S to E}$
2. ${ displaystyle E to (E + E)}$
3. ${ displaystyle E to i}$

крайний левый вывод для ${ Displaystyle ш = ((я + я) + я)}$ является:

${ Displaystyle S { overset {(1)} { Rightarrow}} E { overset {(2)} { Rightarrow}} (E + E) { overset {(2)} { Rightarrow}} ((E + E) + E) { overset {(3)} { Rightarrow}} ((i + E) + E) { overset {(3)} { Rightarrow }} ((i + i) + E) { overset {(3)} { Rightarrow}} ((i + i) + i)}$

Как правило, существует несколько возможностей при выборе правила для раскрытия крайнего левого нетерминала. На шаге 2 предыдущего примера парсер должен выбрать, применять ли правило 2 или правило 3:

${ Displaystyle S { overset {(1)} { Rightarrow}} E { overset {(?)} { Rightarrow}} ?}$

Чтобы быть эффективным, синтаксический анализатор должен иметь возможность делать этот выбор детерминированно, когда это возможно, без поиска с возвратом. Для некоторых грамматик это можно сделать, просматривая непрочитанный ввод (без чтения). В нашем примере, если парсер знает, что следующий непрочитанный символ ${ displaystyle (}$ , единственное правильное правило, которое можно использовать, - 2.

Как правило, ${ Displaystyle LL (к)}$ парсер может смотреть вперед ${ displaystyle k}$ символы. Однако, учитывая грамматику, проблема определения, существует ли ${ Displaystyle LL (к)}$ парсер для некоторых ${ displaystyle k}$ который признает, что это неразрешимо. Для каждого ${ displaystyle k}$, есть язык, который не может быть распознан ${ Displaystyle LL (к)}$ парсером, но может быть ${ Displaystyle LL (к + 1)}$.

Мы можем использовать приведенный выше анализ, чтобы дать следующее формальное определение:

Позволять ${ displaystyle G}$ быть контекстно-свободной грамматикой и ${ Displaystyle к geq 1}$. Мы говорим что ${ displaystyle G}$ является ${ Displaystyle LL (к)}$, тогда и только тогда, когда для любых двух крайних левых выводов:

1. ${ Displaystyle S Rightarrow dots Rightarrow wA alpha Rightarrow dots Rightarrow w beta alpha Rightarrow dots Rightarrow wu}$
2. ${ Displaystyle S Rightarrow точки Rightarrow wA alpha Rightarrow dots Rightarrow w gamma alpha Rightarrow dots Rightarrow wv}$

выполняется условие: префикс строки ${ displaystyle u}$ длины ${ displaystyle k}$ равно префиксу строки ${ displaystyle v}$ длины ${ displaystyle k}$ подразумевает ${ Displaystyle бета = гамма}$.

В этом определении ${ displaystyle S}$ это начальный символ и ${ displaystyle A}$ любой нетерминальный. Уже полученный ввод ${ displaystyle w}$, и еще непрочитанный ${ displaystyle u}$ и ${ displaystyle v}$ строки терминалов. Греческие буквы ${ displaystyle alpha}$, ${ displaystyle beta}$ и ${ displaystyle gamma}$ представляют любую строку как терминалов, так и нетерминалов (возможно, пустую). Длина префикса соответствует размеру буфера просмотра вперед, и в определении говорится, что этого буфера достаточно, чтобы различать любые два производных разных слов.

Парсер

В ${ Displaystyle LL (к)}$ парсер - это детерминированный автомат выталкивания с возможностью взглянуть на следующий ${ displaystyle k}$ вводить символы без чтения. Эту возможность просмотра можно эмулировать, сохраняя содержимое буфера предварительного просмотра в пространстве конечных состояний, поскольку и буфер, и входной алфавит имеют конечный размер. В результате это не делает автомат более мощным, а представляет собой удобную абстракцию.

Алфавит стека ${ Displaystyle Gamma = N чашка Sigma}$, где:

• ${ displaystyle N}$ это множество нетерминалов;
• ${ displaystyle Sigma}$ набор оконечных (входных) символов со специальным символом конца ввода (EOI) ${ Displaystyle $}$.

Стек парсера изначально содержит начальный символ над EOI: ${ Displaystyle [ S $ ]}$. В процессе работы парсер неоднократно заменяет символ ${ displaystyle X}$ на вершине стека:

• с некоторыми ${ displaystyle alpha}$, если ${ displaystyle X in N}$ и есть правило ${ displaystyle X to alpha}$;
• с участием ${ displaystyle epsilon}$ (в некоторых обозначениях ${ displaystyle lambda}$), т.е. ${ displaystyle X}$ извлекается из стека, если ${ Displaystyle X in Sigma}$. В этом случае входной символ ${ displaystyle x}$ читается, и если ${ Displaystyle х neq X}$, парсер отклоняет ввод.

Если последним символом, который нужно удалить из стека, является EOI, синтаксический анализ успешен; автомат принимает через пустой стек.

Состояния и функция перехода явно не указываются; они задаются (генерируются) с помощью более удобного таблица синтаксического анализа вместо. В таблице представлено следующее сопоставление:

• строка: символ вершины стека ${ displaystyle X}$
• столбец: ${ Displaystyle | ш | leq k}$ содержимое буфера просмотра вперед
• ячейка: номер правила для ${ displaystyle X to alpha}$ или ${ displaystyle epsilon}$

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

Конкретный пример

Настроить

Чтобы объяснить работу парсера LL (1), мы рассмотрим следующую небольшую грамматику LL (1):

1. S → F
2. S → (S + F)
3. F → а

и проанализируйте следующий ввод:

(а + а)

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

Каждая ячейка таблицы может указывать максимум на одно правило грамматики (идентифицируемое по его номеру). Например, в таблице синтаксического анализа для приведенной выше грамматики ячейка для нетерминального 'S' и терминального '(' указывает на правило номер 2:

	(	)	а	+	$
S	2	-	1	-	-
F	-	-	3	-	-

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

Процедура разбора

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

Таким образом, на своем первом шаге парсер считывает входной символ '('и символ вершины стека' S '. Инструкция таблицы синтаксического анализа исходит из столбца, озаглавленного входным символом '('и строку, возглавляемую символом вершины стека' S '; эта ячейка содержит «2», что указывает синтаксическому анализатору применить правило (2). Парсер должен переписать 'S' на '( S + F )'в стеке, удалив' S 'из стека и вставив') ',' F ',' + ',' S ',' ('в стек, и на выходе будет записано правило номер 2. Затем стек становится:

[ (, S, +, F, ), $ ]

На втором шаге парсер удаляет '('из входного потока и из своего стека, поскольку теперь они совпадают. Теперь стек становится:

[S, +, F, ), $ ]

Теперь у парсера есть 'а ' на входном потоке и букву «S» на вершине стека. Таблица синтаксического анализа дает указание применить правило (1) из грамматики и записать правило номер 1 в выходной поток. Стек становится:

[F, +, F, ), $ ]

У парсера теперь есть 'а ' на входном потоке и букву F на вершине стека. Таблица синтаксического анализа дает указание применить правило (3) из грамматики и записать правило номер 3 в выходной поток. Стек становится:

[ а, +, F, ), $ ]

У парсера теперь есть 'а ' во входном потоке и 'а' наверху стека. Поскольку они одинаковы, он удаляет его из входного потока и выталкивает из вершины стека. Тогда у парсера есть '+' во входном потоке и '+' находится наверху стека, что означает, что, как и в случае с 'a', он извлекается из стека и удаляется из входного потока. Это приводит к:

[F, ), $ ]

В следующих трех шагах парсер заменит 'F ' в стекеа ', запишите правило номер 3 в выходной поток и удалите 'а ' и ')' как из стека, так и из входного потока. Таким образом, парсер заканчивается на '$' как в его стеке, так и в его входном потоке.

В этом случае синтаксический анализатор сообщит, что он принял входную строку, и запишет следующий список номеров правил в выходной поток:

[ 2, 1, 3, 3 ]

Это действительно список правил для крайний левый вывод входной строки, которая:

S → ( S + F ) → ( F + F ) → (а + F ) → (а + а)

Реализация парсера на C ++

Ниже следует реализация C ++ табличного анализатора LL для примера языка:

#включают <iostream>#включают <map>#включают <stack>перечислить Символы {	// символы:	// Терминальные символы:	TS_L_PARENS,	// (	TS_R_PARENS,	// )	TS_A,		// а	TS_PLUS,	// +	TS_EOS,		// $, в данном случае соответствует ' 0'	TS_INVALID,	// неверный токен	// Нетерминальные символы:	НТС_С,		// S	NTS_F		// F};/*Преобразует действительный токен в соответствующий символ терминала*/Символы лексер(char c){	переключатель (c)	{		кейс '(':  вернуть TS_L_PARENS;		кейс ')':  вернуть TS_R_PARENS;		кейс 'а':  вернуть TS_A;		кейс '+':  вернуть TS_PLUS;		кейс '\0': вернуть TS_EOS; // конец стека: символ $ terminal		по умолчанию:   вернуть TS_INVALID;	}}int основной(int argc, char **argv){	с помощью пространство имен стандартное;	если (argc < 2)	{		cout << "Применение: п  тll '(а + а)' " << конец;		вернуть 0;	}	// Таблица парсера LL, сопоставляет пару <нетерминал, терминал> действию	карта< Символы, карта<Символы, int> > Таблица;	стек<Символы>	сс;	// стек символов	char *п;	// буфер ввода	// инициализируем стек символов	сс.От себя(TS_EOS);	// терминал, $	сс.От себя(НТС_С);		// нетерминальный, S	// инициализируем курсор потока символов	п = &argv[1][0];	// настраиваем таблицу синтаксического анализа	Таблица[НТС_С][TS_L_PARENS] = 2;	Таблица[НТС_С][TS_A] = 1;	Таблица[NTS_F][TS_A] = 3;	в то время как (сс.размер() > 0)	{		если (лексер(*п) == сс.верх())		{			cout << «Соответствующие символы:» << лексер(*п) << конец;			п++;			сс.поп();		}		еще		{			cout << "Правило" << Таблица[сс.верх()][лексер(*п)] << конец;			переключатель (Таблица[сс.верх()][лексер(*п)])			{				кейс 1:	// 1. S → F					сс.поп();					сс.От себя(NTS_F);	// F					перерыв;				кейс 2:	// 2. S → (S + F)					сс.поп();					сс.От себя(TS_R_PARENS);	// )					сс.От себя(NTS_F);		// F					сс.От себя(TS_PLUS);	// +					сс.От себя(НТС_С);		// S					сс.От себя(TS_L_PARENS);	// (					перерыв;				кейс 3:	// 3. F → a					сс.поп();					сс.От себя(TS_A);	// а					перерыв;				по умолчанию:					cout << "таблица разбора по умолчанию" << конец;					вернуть 0;					перерыв;			}		}	}	cout << "закончил разбор" << конец;	вернуть 0;}

Реализация парсера на Python

# Все константы индексируются с 0СРОК = 0ПРАВИЛО = 1# ТерминалыT_LPAR = 0T_RPAR = 1T_A = 2T_PLUS = 3T_END = 4T_INVALID = 5# НетерминалыN_S = 0N_F = 1# Таблица синтаксического анализаТаблица = [[ 1, -1, 0, -1, -1, -1],         [-1, -1, 2, -1, -1, -1]]ПРАВИЛА = [[(ПРАВИЛО, N_F)],         [(СРОК, T_LPAR), (ПРАВИЛО, N_S), (СРОК, T_PLUS), (ПРАВИЛО, N_F), (СРОК, T_RPAR)],         [(СРОК, T_A)]]стек = [(СРОК, T_END), (ПРАВИЛО, N_S)]def lexical_analysis(строка ввода):    Распечатать(«Лексический анализ»)    жетоны = []    для c в строка ввода:        если c   == "+": жетоны.добавить(T_PLUS)        Элиф c == "(": жетоны.добавить(T_LPAR)        Элиф c == ")": жетоны.добавить(T_RPAR)        Элиф c == "а": жетоны.добавить(T_A)        еще: жетоны.добавить(T_INVALID)    жетоны.добавить(T_END)    Распечатать(жетоны)    вернуть жетоныdef syntactic_analysis(жетоны):    Распечатать(«Синтаксический анализ»)    должность = 0    в то время как len(стек) > 0:        (стайп, ценность) = стек.поп()        жетон = жетоны[должность]        если стайп == СРОК:            если ценность == жетон:                должность += 1                Распечатать("поп", ценность)                если жетон == T_END:                    Распечатать("ввод принят")            еще:                Распечатать("плохой термин на вводе:", жетон)                перерыв        Элиф стайп == ПРАВИЛО:            Распечатать("значение", ценность, "токен", жетон)            правило = Таблица[ценность][жетон]            Распечатать("правило", правило)            для р в перевернутый(ПРАВИЛА[правило]):                стек.добавить(р)        Распечатать("стек", стек)строка ввода = "(а + а)"syntactic_analysis(lexical_analysis(строка ввода))

Замечания

Как видно из примера, парсер выполняет три типа шагов в зависимости от того, является ли вершина стека нетерминалом, терминалом или специальным символом. $:

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

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

Создание таблицы синтаксического анализа LL (1)

Чтобы заполнить таблицу синтаксического анализа, мы должны установить, какое правило грамматики следует выбрать синтаксическому анализатору, если он видит нетерминальный А наверху его стопки и символ а на входном потоке. Легко видеть, что такое правило должно иметь вид А → ш и что язык, соответствующий ш должна иметь хотя бы одну строку, начинающуюся с а. Для этого определим Первый сет из шздесь написано как Fi(ш), как набор терминалов, которые можно найти в начале некоторой строки в ш, плюс ε, если пустая строка также принадлежит ш.Данная грамматика с правилами А₁ → ш₁, ..., А_п → ш_п, мы можем вычислить Fi(ш_я) и Fi(А_я) для каждого правила следующим образом:

1. инициализировать каждый Fi(А_я) с пустым множеством
2. добавить Fi (ш_я) к Fi(А_я) для каждого правила А_я → ш_я, где Fi определяется следующим образом:
   • Fi (ау ') = { а } для каждого терминала а
   • Fi (Ой ') = Fi(А) для каждого нетерминального А с ε не в Fi(А)
   • Fi (Ой ' ) = (Fi(А) {ε}) ∪ Fi (w ' ) для каждого нетерминального А с ε в Fi(А)
   • Fi (ε) = {ε}
3. добавить Fi (ш_я) к Fi(А_я) для каждого правила А_я → ш_я
4. выполните шаги 2 и 3, пока все Fi наборы остаются прежними.

Результатом является решение с наименьшей фиксированной точкой для следующей системы:

• Fi(А) ⊇ Fi(ш) для каждого правила A → ш
• Fi(а) ⊇ { а } для каждого терминала а
• Fi(ш₀ ш₁) ⊇ Fi(ш₀)·Fi(ш₁), для всех слов ш₀ и ш₁
• Fi(ε) ⊇ {ε}

где для наборов слов U и V усеченное произведение определяется как U · V = {(uv): 1: u ∈ U, v ∈ V}, а w: 1 обозначает начальный префикс длины 1 слов w длины 2 или более или самого w, если длина w равна 0 или 1.

К сожалению, первых наборов недостаточно для вычисления таблицы синтаксического анализа, потому что правая часть ш правила могут быть в конечном итоге переписаны в пустую строку, поэтому синтаксический анализатор также должен использовать правило А → ш если ε находится в Fi(ш) и видит во входном потоке символ, который может следовать за А. Следовательно, нам также понадобится Follow-set из А, записанный как Fo(А) здесь, который определяется как набор клемм а так что есть строка символов αAaβ который может быть получен из начального символа. Мы используем $ как специальный терминал, указывающий конец входного потока, и S как начальный символ.

Вычисление Follow-множеств для нетерминалов в грамматике может быть выполнено следующим образом:

1. инициализировать Fo(S) с участием { $ } и все остальные Fo(А_я) с пустым множеством
2. если есть правило формы А_j → wA_яw ' , тогда
   • если терминал а в Fi(w ' ), затем добавьте а к Fo(А_я)
   • если ε находится в Fi(w ' ), затем добавьте Fo(А_j) к Fo(А_я)
   • если w ' имеет длину 0, затем добавьте Fo(А_j) к Fo(А_я)
3. повторите шаг 2, пока все Fo наборы остаются прежними.

Это обеспечивает решение с наименьшей фиксированной точкой для следующей системы:

• Fo(S) ⊇ {$}
• Fo(А) ⊇ Fi(ш)·Fo(B) для каждого правила вида B → ... A w

Теперь мы можем точно определить, какие правила будут отображаться в таблице синтаксического анализа. Т[А, а] обозначает запись в таблице для нетерминального А и терминал а, тогда

Т[А,а] содержит правило А → ш если и только если

а в Fi(ш) или

ε находится в Fi(ш) и а в Fo(А).

Эквивалентно: Т[А, а] содержит правило А → ш для каждого а ∈ Fi(ш)·Fo(А).

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

Построение ЛЛ (k) таблица синтаксического анализа

Конструкция парсеров LL (1) может быть адаптирована к LL (k) для k > 1 со следующими модификациями:

• усеченное произведение определяется как U · V = {(uv): k: u ∈ U, v ∈ V}, где w: k обозначает начальный префикс длины k слов длины> k или самого слова w, если w имеет длину k или меньше,
• Fo(S) = {$^k}

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

До середины 1990-х было широко распространено мнение, что LL (k) синтаксический анализ (для k > 1) было непрактично,^{[нужна цитата ]} так как таблица парсера будет иметь экспоненциальный размер в k в худшем случае. Это восприятие постепенно изменилось после выпуска Набор инструментов для построения компилятора Purdue примерно в 1992 году, когда было продемонстрировано, что многие языки программирования может быть эффективно проанализирован LL (k), не вызывая наихудшего поведения анализатора. Более того, в некоторых случаях анализ LL возможен даже при неограниченном просмотре вперед. Напротив, традиционные генераторы парсеров, такие как yacc использовать LALR (1) таблицы парсера для построения ограниченного Парсер LR с фиксированным просмотром вперед по одному токену.

Конфликты

Как описано во введении, анализаторы LL (1) распознают языки с грамматиками LL (1), которые являются частным случаем контекстно-свободных грамматик; Парсеры LL (1) не могут распознавать все контекстно-свободные языки. Языки LL (1) представляют собой собственное подмножество языков LR (1), которые, в свою очередь, являются надлежащим подмножеством всех контекстно-свободных языков. Чтобы контекстно-свободная грамматика была грамматикой LL (1), не должно возникать определенных конфликтов, которые мы описываем в этом разделе.

Терминология^[11]

Позволять А быть нетерминальным. ПЕРВЫЙ(А) представляет собой (определяется как) набор терминалов, которые могут появляться в первой позиции любой строки, полученной из А. СЛЕДОВАТЬ(А) является объединением над: (1) ПЕРВЫЙ (B) где B любой нетерминальный, который следует непосредственно за А в правой части правило производства, и (2) СЛЕДУЙТЕ (B) где B любой руководитель правила формы B → wA.

LL (1) конфликты

Существует два основных типа конфликтов LL (1):

ПЕРВЫЙ / ПЕРВЫЙ конфликт

FIRST устанавливает два разных правила грамматики для одного и того же нетерминального пересечения. Пример конфликта LL (1) FIRST / FIRST:

S -> E | E 'a'E ->' b '| ε

ПЕРВЫЙ(E) = {б, ε} и ПЕРВЫЙ (E а) = {б, а}, поэтому при отрисовке таблицы возникает конфликт в терминале б правила производства S.

Частный случай: левая рекурсия

Левая рекурсия вызовет конфликт FIRST / FIRST со всеми альтернативами.

E -> E '+' термин | alt1 | alt2

Конфликт FIRST / FOLLOW

Наборы FIRST и FOLLOW правила грамматики перекрываются. С пустой строки (ε) в ПЕРВОМ наборе неизвестно, какую альтернативу выбрать. Пример конфликта LL (1):

S -> A 'a' 'b'A ->' a '| ε

ПЕРВЫЙ набор А сейчас {а, ε} и множество FOLLOW {а}.

Решения конфликтов LL (1)

Левый факторинг

Обычный левый фактор «исключен».

А -> Х | X Y Z

становится

A -> X BB -> Y Z | ε

Может применяться, когда две альтернативы начинаются с одного и того же символа, например, конфликт ПЕРВЫЙ / ПЕРВЫЙ.

Другой пример (более сложный) с использованием приведенного выше примера конфликта FIRST / FIRST:

S -> E | E 'a'E ->' b '| ε

становится (слияние в единый нетерминал)

S -> 'b' | ε | 'b' 'a' | 'а'

затем через левый факторинг становится

S -> 'b' E | EE -> 'а' | ε

Замена

Подстановка правила в другое для устранения косвенных конфликтов или конфликтов FIRST / FOLLOW. Обратите внимание, что это может вызвать конфликт FIRST / FIRST.

Удаление левой рекурсии^[12]

Для общего метода см. удаление левой рекурсии.Простой пример удаления левой рекурсии: следующее производственное правило оставило рекурсию на E

E -> E '+' TE -> Т

Это правило представляет собой не что иное, как список Ts, разделенных знаком «+». В форме регулярного выражения T ('+' T) *. Таким образом, правило можно переписать как

E -> T ZZ -> '+' T ZZ -> ε

Теперь нет левой рекурсии и нет конфликтов ни по одному из правил.

Однако не все контекстно-свободные грамматики имеют эквивалентную LL (k) -грамматику, например:

S -> A | BA -> 'a' A 'b' | εB -> 'a' B 'b' 'b' | ε

Можно показать, что не существует никакой LL (k) -грамматики, принимающей язык, порожденный этой грамматикой.

Смотрите также

• Сравнение генераторов парсеров
• Дерево синтаксического анализа
• Анализ сверху вниз
• Анализ снизу вверх

Заметки

внешние ссылки

• Учебник по реализации парсеров LL (1) на C # (в архиве)
• Симулятор синтаксического анализа Этот тренажер используется для создания таблиц синтаксического анализа LL (1) и решения упражнений книги.
• LL (1) DSL PEG parser (фреймворк инструментария)
• Теоретико-языковое сравнение грамматик LL и LR
• LL (k) Теория синтаксического анализа