LL-парсер

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

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

Парсер LL называется LL-регулярным (LLR), если он анализирует LL-регулярный язык . Класс LLR-грамматик содержит каждую LL(k)-грамматику для каждого k. Для каждой грамматики LLR существует анализатор LLR, который анализирует грамматику за линейное время.

Двумя номенклативными типами анализаторов выбросов являются LL(*) и LL(finite). Синтаксический анализатор называется LL(*)/LL(finite), если он использует стратегию анализа LL(*)/LL(finite). Парсеры LL(*) и LL(finite) функционально ближе к парсерам PEG . Синтаксический анализатор LL(конечный) может оптимально анализировать произвольную грамматику LL(k) по количеству предварительных и предварительных сравнений. Класс грамматик, анализируемых с помощью стратегии LL(*), охватывает некоторые контекстно-зависимые языки из-за использования синтаксических и семантических предикатов и не идентифицирован. Было высказано предположение, что анализаторы LL(*) лучше рассматривать как анализаторы TDPL . Вопреки распространенному заблуждению, парсеры LL(*) в целом не являются LLR, и их конструкция гарантирует худшую производительность в среднем (суперлинейность по отношению к линейному времени) и гораздо худшую в худшем случае (экспоненциальность по отношению к линейному времени).

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

Обзор

Для данной контекстно-свободной грамматики синтаксический анализатор пытается найти самое левое дифференцирование .Приведен пример грамматики $G$:

1. $S\to E$
2. $E\to (E+E)$
3. $E\to i$

самый левый вывод для $w=((i+i)+i)$ является:

$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:

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

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

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

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

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

1. $S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu$
2. $S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv$

выполняется следующее условие: префикс строки $u$ длины $k$ равен префиксу строки $v$ длины $k$ подразумевает $\beta \ =\ \gamma$.

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

Парсер

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

Алфавит стека $\Gamma =N\cup \Sigma$, где:

• $N$ – множество нетерминалов;
• $\Sigma$ набор терминальных (входных) символов со специальным символом конца ввода (EOI) $\$$.

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

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

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

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

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

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

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

Настраивать

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

1. С → Ж
2. С → ( С + Ж )
3. Ф → а

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

(а + а)

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

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

	(	)	а	+	$
С	2	—	1	—	—
Ф	—	—	3	—	—

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

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

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

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

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

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

[ S, +, F, ), $ ]

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

[ F, +, F, ), $ ]

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

[ a, +, F, ), $ ]

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

[ F, ), $ ]

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

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

[ 2, 1, 3, 3 ]

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

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

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

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

#include <iostream>#include <map>#include <stack>enum Symbols {	// the symbols:	// Terminal symbols:	TS_L_PARENS,	// (	TS_R_PARENS,	// )	TS_A,		// a	TS_PLUS,	// +	TS_EOS,		// $, in this case corresponds to '\0'	TS_INVALID,	// invalid token	// Non-terminal symbols:	NTS_S,		// S	NTS_F		// F};/*Converts a valid token to the corresponding terminal symbol*/Symbols lexer(char c){	switch (c)	{		case '(':  return TS_L_PARENS;		case ')':  return TS_R_PARENS;		case 'a':  return TS_A;		case '+':  return TS_PLUS;		case '\0': return TS_EOS; // end of stack: the $ terminal symbol		default:   return TS_INVALID;	}}int main(int argc, char **argv){	using namespace std;	if (argc < 2)	{		cout << "usage:\n\tll '(a+a)'" << endl;		return 0;	}	// LL parser table, maps < non-terminal, terminal> pair to action	map< Symbols, map<Symbols, int> > table;	stack<Symbols>	ss;	// symbol stack	char *p;	// input buffer	// initialize the symbols stack	ss.push(TS_EOS);	// terminal, $	ss.push(NTS_S);		// non-terminal, S	// initialize the symbol stream cursor	p = &argv[1][0];	// set up the parsing table	table[NTS_S][TS_L_PARENS] = 2;	table[NTS_S][TS_A] = 1;	table[NTS_F][TS_A] = 3;	while (ss.size() > 0)	{		if (lexer(*p) == ss.top())		{			cout << "Matched symbols: " << lexer(*p) << endl;			p++;			ss.pop();		}		else		{			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;			switch (table[ss.top()][lexer(*p)])			{				case 1:	// 1. S → F					ss.pop();					ss.push(NTS_F);	// F					break;				case 2:	// 2. S → ( S + F )					ss.pop();					ss.push(TS_R_PARENS);	// )					ss.push(NTS_F);		// F					ss.push(TS_PLUS);	// +					ss.push(NTS_S);		// S					ss.push(TS_L_PARENS);	// (					break;				case 3:	// 3. F → a					ss.pop();					ss.push(TS_A);	// a					break;				default:					cout << "parsing table defaulted" << endl;					return 0;			}		}	}	cout << "finished parsing" << endl;	return 0;}

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

# All constants are indexed from 0TERM = 0RULE = 1# TerminalsT_LPAR = 0T_RPAR = 1T_A = 2T_PLUS = 3T_END = 4T_INVALID = 5# Non-TerminalsN_S = 0N_F = 1# Parse tabletable = [[ 1, -1, 0, -1, -1, -1],         [-1, -1, 2, -1, -1, -1]]RULES = [[(RULE, N_F)],         [(TERM, T_LPAR), (RULE, N_S), (TERM, T_PLUS), (RULE, N_F), (TERM, T_RPAR)],         [(TERM, T_A)]]stack = [(TERM, T_END), (RULE, N_S)]def lexical_analysis(inputstring: str) -> list:    print("Lexical analysis")    tokens = []    for c in inputstring:        if c   == "+": tokens.append(T_PLUS)        elif c == "(": tokens.append(T_LPAR)        elif c == ")": tokens.append(T_RPAR)        elif c == "a": tokens.append(T_A)        else: tokens.append(T_INVALID)    tokens.append(T_END)    print(tokens)    return tokensdef syntactic_analysis(tokens: list) -> None:    print("Syntactic analysis")    position = 0    while len(stack) > 0:        (stype, svalue) = stack.pop()        token = tokens[position]        if stype == TERM:            if svalue == token:                position += 1                print("pop", svalue)                if token == T_END:                    print("input accepted")            else:                print("bad term on input:", token)                break        elif stype == RULE:            print("svalue", svalue, "token", token)            rule = table[svalue][token]            print("rule", rule)            for r in reversed(RULES[rule]):                stack.append(r)        print("stack", stack)inputstring = "(a+a)"syntactic_analysis(lexical_analysis(inputstring))

Примечания

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

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

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

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

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

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

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

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

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

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

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

1. инициализировать Fo ( S ) с помощью { $ } и каждый другой Fo ( A _i ) с пустым набором
2. если существует правило вида A _j → wA _i w' , то
   • если терминал a находится в Fi ( w' , то добавьте a к Fo ( Ai ₎ )
   • если ε находится в Fi ( w' ), то добавьте Fo ( A _j ) к Fo ( A _i )
   • если w' имеет длину 0, то добавьте Fo ( A _j ) к Fo ( A _i )
3. повторяйте шаг 2, пока все наборы Fo не останутся прежними.

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

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

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

T [ A , a ] содержит правило A → w тогда и только тогда, когда

a находится в Fi ( w ) или

ε находится в Fi ( w ), а a находится в Fo ( A ).

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

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

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

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

• усеченный продукт определен $U\cdot V=\{(uv):k\mid u\in U,v\in V\}$, где w:k обозначает начальный префикс длины k слов длины > k или сам w, если w имеет длину k или меньше,
• Fo ( S ) = { $ ^к }
• Применить Fi (ab) = Fi (a) $\cdot$Fi (β) также на шаге 2 конструкции Fi , данной для LL(1).
• На шаге 2 конструкции Fo для A _j → wA _i w' просто добавьте Fi ( w' ) $\cdot$Fo ( Aj _Fo ) есть ( Ai ₎ .

где ввод сопровождается k конечными маркерами $ , чтобы полностью учесть k контекст просмотра. Этот подход исключает особые случаи для ε и может быть одинаково хорошо применен в случае LL(1).

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

Конфликты

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

Терминология

Пусть A — нетерминал. FIRST( A ) — это (определенный как) набор терминалов, которые могут появляться в первой позиции любой строки, полученной из A . FOLLOW( A ) — это объединение:

1. FIRST( B ), где B — любой нетерминал, который следует сразу за A в правой части производственного правила .
2. FOLLOW( B ), где B — любой заголовок правила вида B → wA .

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

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

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

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

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

FIRST( E ) = { b , ε} и FIRST( E a ) = { b , a }, поэтому при рисовании таблицы возникает конфликт на терминале b производственного S. правила

Особый случай: левая рекурсия

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

E -> E '+' term | alt1 | alt2

Конфликт ПЕРВОГО/ПОСЛЕДУЮЩЕГО

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

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

ПЕРВЫЙ набор A — это { a , ε}, а ПОСЛЕДУЮЩИЙ набор — { a }.

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

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

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

A -> X | X Y Z

становится

A -> X BB -> Y Z | ε

Может применяться, когда две альтернативы начинаются с одного и того же символа, например конфликт FIRST/FIRST.

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

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

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

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

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

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

Замена

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

Удаление левой рекурсии

Видеть.

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

E -> E '+' TE -> T

Это правило представляет собой не что иное, как список букв T, разделенных знаком «+». В регулярном выражении формы 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 и LR
• LL(k) Теория синтаксического анализа