В компьютерной науке , с LL парсер (слева направо, левое порождение) является сверху вниз анализатор для подмножества контекстно-свободных языков . Он анализирует входной сигнал из L EFT направо, выполняя л eftmost вывод предложения.
LL - анализатор называется LL ( K ) парсер если он использует K лексемы из опережающего просмотра при разборе предложения. Грамматика называется грамматикой LL ( k ), если из нее можно построить анализатор LL ( k ). Формальный язык называется языком LL ( k ), если он имеет грамматику LL ( k ). Набор языков LL ( k ) надлежащим образом содержится в наборе языков LL ( k +1) для каждого k ≥ 0. Следствием этого является то, что не все контекстно-свободные языки могут быть распознаны анализатором LL ( k ). .
LL-синтаксический анализатор называется LL-регулярным, если он анализирует в точности класс LL-регулярных языков. LLR-грамматики являются собственным надмножеством LL (k) грамматик для любого k. Для каждой грамматики LLR существует анализатор LLR, который анализирует грамматику за линейное время.
Двумя номенклатурными типами анализатора выбросов являются LL (*) и LL (конечный). Парсер называется LL (*) / LL (конечный), если он использует стратегию синтаксического анализа LL (*) / LL (конечный). Анализаторы LL (*) и LL (конечные) функционально более похожи на синтаксические анализаторы PEG . Анализатор LL (конечный) может анализировать произвольную грамматику LL (k) оптимальным образом с точки зрения количества предварительных и предварительных сравнений. Класс грамматик, анализируемых стратегией LL (*), включает некоторые контекстно-зависимые языки из-за использования синтаксических и семантических предикатов и не был идентифицирован. Было высказано предположение, что парсеры LL (*) лучше рассматривать как парсеры TDPL . Вопреки распространенному заблуждению, парсеры LL (*) не являются LLR в целом, и конструкция гарантирует, что они будут работать хуже в среднем (суперлинейное по отношению к линейному времени) и намного хуже в худшем случае (экспоненциальное по отношению к линейному времени).
Грамматики LL, особенно грамматики LL (1), представляют большой практический интерес, поскольку синтаксические анализаторы для этих грамматик легко конструируются, и по этой причине многие компьютерные языки спроектированы как LL (1). Парсеры LL - это парсеры на основе таблиц, похожие на парсеры LR . Грамматики LL также можно анализировать с помощью синтаксических анализаторов с рекурсивным спуском . Согласно Уэйту и Гусу (1984), грамматики LL ( k ) были введены Стернсом и Льюисом (1969).
1 Обзор
2 Парсер
3 Конкретный пример
3.1 Настройка
3.2 Процедура парсинга
3.3 Реализация парсера на C ++
3.4 Реализация парсера в Python
4 Замечания
5 Построение таблицы синтаксического анализа LL (1)
6 Построение таблицы синтаксического анализа LL ( k )
7 Конфликты
7.1 Терминология [11]
7.2 LL (1) конфликты
7.2.1 Конфликт ПЕРВЫЙ / ПЕРВЫЙ
7.2.1.1 Частный случай: левая рекурсия
7.2.2 Конфликт FIRST / FOLLOW
7.3 Решение конфликтов LL (1)
7.3.1 Левый факторинг
7.3.2 Замена
7.3.3 Удаление левой рекурсии [12]
8 См. Также
9 Примечания
10 Внешние ссылки
Обзор
Для данной контекстно-свободной грамматики синтаксический анализатор пытается найти крайний левый вывод . Учитывая пример грамматики :
грамм
{\ displaystyle G}
→
E
{\ displaystyle S \ to E}
E
→
(
E
+
E
)
{\ displaystyle E \ to (E + E)}
E
→
я
{\ displaystyle E \ to i}
крайний левый вывод для :
ш
знак равно
(
(
я
+
я
)
+
я
)
{\ Displaystyle ш = ((я + я) + я)}
⇒
(
1
)
E
⇒
(
2
)
(
E
+
E
)
⇒
(
2
)
(
(
E
+
E
)
+
E
)
⇒
(
3
)
(
(
я
+
E
)
+
E
)
⇒
(
3
)
(
(
я
+
я
)
+
E
)
⇒
(
3
)
(
(
я
+
я
)
+
я
)
{\ 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:
⇒
(
1
)
E
⇒
(
?
)
?
{\ Displaystyle S \ {\ overset {(1)} {\ Rightarrow}} \ E \ {\ overset {(?)} {\ Rightarrow}} \?}
Чтобы быть эффективным, синтаксический анализатор должен иметь возможность делать этот выбор детерминированно, когда это возможно, без поиска с возвратом. Для некоторых грамматик это можно сделать, просмотрев непрочитанный ввод (без чтения). В нашем примере, если синтаксический анализатор знает, что следующий непрочитанный символ , единственное правильное правило, которое можно использовать, - 2.
(
{\ displaystyle (}
Как правило, синтаксический анализатор может смотреть вперед на символы. Однако с учетом грамматики проблема определения, существует ли для некоторых парсер , распознающий его, неразрешима. Для каждого есть язык, который не может быть распознан парсером, но может быть распознан .
L
L
(
k
)
{\ Displaystyle LL (к)}
k
{\ displaystyle k}
L
L
(
k
)
{\ Displaystyle LL (к)}
k
{\ displaystyle k}
k
{\ displaystyle k}
L
L
(
k
)
{\ Displaystyle LL (к)}
L
L
(
k
+
1
)
{\ Displaystyle LL (к + 1)}
Мы можем использовать приведенный выше анализ, чтобы дать следующее формальное определение:
Позвольте быть контекстно-свободной грамматике и . Мы говорим, что есть , тогда и только тогда, когда для любых двух крайних левых выводов:
грамм
{\ displaystyle G}
k
≥
1
{\ Displaystyle к \ geq 1}
грамм
{\ displaystyle G}
L
L
(
k
)
{\ Displaystyle LL (к)}
⇒
⋯
⇒
ш
А
α
⇒
⋯
⇒
ш
β
α
⇒
⋯
⇒
ш
ты
{\ Displaystyle S \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wA \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ w \ beta \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wu}
S
⇒
⋯
⇒
ш
А
α
⇒
⋯
⇒
ш
γ
α
⇒
⋯
⇒
ш
v
{\ Displaystyle S \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wA \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ w \ gamma \ alpha \ \ Rightarrow \ \ cdots \ \ Rightarrow \ wv}
выполняется следующее условие: префикс строки длины равен префиксу строки подразумеваемой длины .
ты
{\ displaystyle u}
k
{\ displaystyle k}
v
{\ displaystyle v}
k
{\ displaystyle k}
β
знак равно
γ
{\ Displaystyle \ бета \ = \ \ гамма}
В этом определении - это начальный символ и любой нетерминальный символ . Уже полученный вход , и все же непрочитанные и являются строки терминалов. Греческие буквы , и представляют собой любую последовательность обоих терминалов и нетерминалов (возможно , пустой). Длина префикса соответствует размеру опережающего буфера, и в определении говорится, что этого буфера достаточно, чтобы различать любые два производных разных слов.
S
{\ displaystyle S}
А
{\ displaystyle A}
ш
{\ displaystyle w}
ты
{\ displaystyle u}
v
{\ displaystyle v}
α
{\ displaystyle \ alpha}
β
{\ displaystyle \ beta}
γ
{\ displaystyle \ gamma}
Анализатор представляет собой детерминированный магазинный автомат с возможностью заглядывать на следующих входных символов без чтения. Эту возможность просмотра можно эмулировать, сохраняя содержимое буфера предварительного просмотра в пространстве конечных состояний, поскольку и буфер, и входной алфавит имеют конечный размер. В результате это не делает автомат более мощным, а представляет собой удобную абстракцию.
L
L
(
k
)
{\ Displaystyle LL (к)}
k
{\ displaystyle k}
Алфавит стека , где:
Γ
знак равно
N
∪
Σ
{\ Displaystyle \ Gamma = N \ чашка \ Sigma}
{\ displaystyle N}
это множество нетерминалов;
Σ
{\ displaystyle \ Sigma}
набор оконечных (входных) символов со специальным символом конца ввода (EOI) .
$
{\ Displaystyle \ $}
Стек анализатора изначально содержит начальный символ над ВЗ: . Во время работы парсер неоднократно заменяет символ на вершине стека:
[
S
$
]
{\ Displaystyle [\ S \ \ $ \]}
Икс
{\ displaystyle X}
α
{\ displaystyle \ alpha}
Икс
∈
N
{\ 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}
столбец: содержимое буфера просмотра вперед
|
ш
|
≤
k
{\ Displaystyle | ш | \ leq k}
ячейка: номер правила для или
Икс
→
α
{\ displaystyle X \ to \ alpha}
ϵ
{\ displaystyle \ epsilon}
Если синтаксический анализатор не может выполнить допустимый переход, ввод отклоняется (пустые ячейки). Чтобы сделать таблицу более компактной, обычно отображаются только нетерминальные строки, так как действие одинаково для терминалов.
Настраивать
Чтобы объяснить работу парсера LL (1), мы рассмотрим следующую небольшую грамматику LL (1):
S → (S + F)
F → а
и проанализируйте следующий ввод:
Таблица синтаксического анализа LL (1) для грамматики имеет строку для каждого из нетерминалов и столбец для каждого терминала (включая специальный терминал, представленный здесь как $ , который используется для обозначения конца входного потока).
Каждая ячейка таблицы может указывать максимум на одно правило грамматики (идентифицируемое по его номеру). Например, в таблице синтаксического анализа для приведенной выше грамматики ячейка для нетерминального 'S' и терминального '(' указывает на правило номер 2:
| ( | ) | а | + | $ | |
|---|---|---|---|---|---|
| S | 2 | - | 1 | - | - |
| F | - | - | 3 | - | - |
Алгоритм построения таблицы синтаксического анализа описан в следующем разделе, но сначала давайте посмотрим, как синтаксический анализатор использует таблицу синтаксического анализа для обработки входных данных.
На каждом этапе синтаксический анализатор считывает следующий доступный символ из входного потока и самый верхний символ из стека. Если входной символ и символ вершины стека совпадают, синтаксический анализатор отбрасывает их оба, оставляя только несовпадающие символы во входном потоке и в стеке.
Таким образом, на своем первом шаге синтаксический анализатор считывает входной символ ' ( ' и символ вершины стека 'S'. Инструкция таблицы синтаксического анализа поступает из столбца, возглавляемого входным символом ' ( ', и строки, возглавляемой стеком- верхний символ ""S""; эта ячейка содержит ""2"", который указывает синтаксическому анализатору применить правило (2). Анализатор должен переписать ""S"" в "" ( S + F ) "" в стеке, удалив ""S"" из стека. и нажимая ')', 'F', '+', 'S', '(' в стек, и это записывает правило номер 2 в вывод. Затем стек становится:
На втором этапе синтаксический анализатор удаляет символ ' ( ' из входного потока и из своего стека, поскольку теперь они совпадают. Теперь стек становится следующим:
Теперь синтаксический анализатор имеет "" a"" на входном потоке и ""S"" на вершине стека. Таблица синтаксического анализа инструктирует его применить правило (1) из грамматики и записать правило номер 1 в выходной поток. Стек становится:
Теперь синтаксический анализатор имеет "" a"" на входном потоке и ""F"" на вершине стека. Таблица синтаксического анализа инструктирует его применить правило (3) из грамматики и записать правило номер 3 в выходной поток. Стек становится:
Теперь синтаксический анализатор имеет "" a"" во входном потоке и ""a"" на вершине стека. Поскольку они одинаковы, он удаляет его из входного потока и выталкивает из вершины стека. Анализатор затем имеет « +» на входной поток и «+» , находится в верхней части стека значения, как и с «а», она извлекается из стека и удаляется из входного потока. Это приводит к:
В следующих трех шагах синтаксический анализатор заменит « F» в стеке на « a» , запишет правило номер 3 в выходной поток и удалит « a» и « )» как из стека, так и из входного потока. Таким образом, синтаксический анализатор заканчивается символом « $» как в стеке, так и в входном потоке.
В этом случае синтаксический анализатор сообщит, что он принял входную строку, и запишет следующий список номеров правил в выходной поток:
Это действительно список правил для самого левого вывода входной строки, а именно:
Реализация парсера на C ++
Ниже следует реализация C ++ табличного анализатора LL для примера языка:
#include
#include
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 pair to action
map< Symbols, map > table;
stack 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 0
TERM = 0
RULE = 1
# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5
# Non-Terminals
N_S = 0
N_F = 1
# Parse table
table = [[ 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):
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 tokens
def syntactic_analysis(tokens):
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))
Замечания
Как видно из примера, парсер выполняет три типа шагов в зависимости от того, является ли вершина стека нетерминалом, терминалом или специальным символом $ :
Если верхняя часть является терминалом, то синтаксический анализатор сравнивает ее с символом во входном потоке, и, если они равны, они оба удаляются. Если они не равны, парсер сообщает об ошибке и останавливается.
Если вверху стоит $, а во входном потоке также есть знак $, то синтаксический анализатор сообщает, что он успешно проанализировал ввод, в противном случае он сообщает об ошибке. В обоих случаях парсер остановится.
Эти шаги повторяются до тех пор, пока синтаксический анализатор не остановится, а затем он либо полностью проанализирует ввод и запишет крайнюю левую производную в выходной поток, либо сообщит об ошибке.
Чтобы заполнить таблицу синтаксического анализа, мы должны установить, какое правило грамматики следует выбрать синтаксическому анализатору, если он видит нетерминал A на вершине своего стека и символ a в своем входном потоке. Легко видеть, что такое правило должно иметь вид A → w и что язык, соответствующий w, должен иметь хотя бы одну строку, начинающуюся с a . Для этого мы определим первый-набор из ж , здесь написано , как Fi ( ж ), как множество терминалов , которые могут быть найдены в начале некоторой строки в ш , плюс е , если пустая строка также принадлежит ш . Учитывая грамматику с правилами A 1 → w 1 ,…, A n → w n , мы можем вычислить Fi ( w i ) и Fi ( A i ) для каждого правила следующим образом:
добавить 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 (ε) = {ε}
добавить Fi ( w i ) к Fi ( A i ) для каждого правила A i → w i
выполните шаги 2 и 3, пока все наборы Fi не останутся прежними.
Результатом является решение с наименьшей фиксированной точкой для следующей системы:
Fi ( a ) ⊇ { a }, для каждого терминала a
Fi ( w 0 w 1 ) ⊇ Fi ( w 0 ) · Fi ( w 1 ) для всех слов w 0 и w 1
Fi (ε) ⊇ {ε}
где для наборов слов U и V усеченное произведение определяется как U · V = {(uv): 1: u ∈ U, v ∈ V}, а w: 1 обозначает начальный префикс длины 1 слов w длиной 2 или более, или сам w, если длина w равна 0 или 1.
К сожалению, первых наборов недостаточно для вычисления таблицы синтаксического анализа. Это связано с тем, что правая часть правила w в конечном итоге может быть переписана в пустую строку. Таким образом, анализатор должен также использовать правило A → W , если ε находится в Fi ( ж ) , и он видит на входном потоке символ , который может следовать A . Таким образом, мы также нуждаемся в Follow-набор из А , записывается в виде Фо ( А ) здесь, который определяется как множество терминалов таким образом, что есть строка символов αAaβ , которые могут быть получены из начального символа. Мы используем $ как специальный терминал, указывающий конец входного потока, и S как начальный символ.
Вычисление Follow-множеств для нетерминалов в грамматике может быть выполнено следующим образом:
если существует правило вида A j → wA i w ' , то
если терминал a находится в Fi ( w ' ), то добавьте a к Fo ( A i )
если ε принадлежит Fi ( w ' ), то добавить Fo ( A j ) к Fo ( A i )
если w ' имеет длину 0, то добавить Fo ( A j ) к Fo ( A i )
повторяйте шаг 2, пока все наборы Fo не останутся прежними.
Это обеспечивает решение с наименьшей фиксированной точкой для следующей системы:
Fo ( A ) ⊇ Fi ( w ) · Fo ( B ) для каждого правила вида B → ... A w
Теперь мы можем точно определить, какие правила будут отображаться в таблице синтаксического анализа. Если T [ A , a ] обозначает запись в таблице для нетерминала A и терминала a , то
a находится в Fi ( w ) или
е принадлежит Fi ( w ), а a принадлежит Fo ( A ).
Эквивалентно: T [ A , a ] содержит правило A → w для каждого a ∈ Fi ( w ) · Fo ( A ).
Если таблица содержит не более одного правила в каждой из своих ячеек, то синтаксический анализатор всегда будет знать, какое правило он должен использовать, и поэтому может анализировать строки без возврата. Это именно в этом случае , что грамматика называется LL (1) грамматикой .
Конструкция парсеров LL (1) может быть адаптирована к LL ( k ) для k > 1 со следующими изменениями:
Fo ( S ) = { $ k }
где к входу добавляется суффикс k конечных маркеров $ , чтобы полностью учесть k контекста опережающего просмотра.
До середины 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 нетерминал. ПЕРВЫЙ ( ) является (назовем) множество терминалов , которые могут появиться в первой позиции любой строки , полученной из A . FOLLOW ( A ) - это объединение над: (1) FIRST ( B ), где B - любой нетерминальный элемент, который следует сразу за A в правой части производственного правила , и (2) FOLLOW ( B ), где B - любое глава правила вида B → wA .
Существует два основных типа конфликтов LL (1):
ПЕРВЫЙ набор двух разных грамматических правил для одного и того же нетерминального пересечения. Пример конфликта LL (1) ПЕРВЫЙ / ПЕРВЫЙ:
E -> 'b' | ε
ПЕРВЫЙ ( Е ) = { Ь , ε} , и первый ( Е ) = { Ь , }, поэтому , когда таблица обращаются, возникает конфликт под терминалом б из правил производства S .
Левая рекурсия вызовет конфликт FIRST / FIRST со всеми альтернативами.
Конфликт FIRST / FOLLOW
Наборы FIRST и FOLLOW правила грамматики перекрываются. При пустой строке (ε) в ПЕРВОМ наборе неизвестно, какую альтернативу выбрать. Пример конфликта LL (1):
A -> 'a' | ε
ПЕРВЫЙ набор A теперь равен { a , ε}, а набор FOLLOW - { a }.
Левый факторинг
Обычный левый фактор «исключен».
становится
B -> Y Z | ε
Может применяться, когда две альтернативы начинаются с одного и того же символа, например, конфликт ПЕРВЫЙ / ПЕРВЫЙ.
Другой пример (более сложный) с использованием приведенного выше примера конфликта FIRST / FIRST:
E -> 'b' | ε
становится (слияние в единый нетерминал)
затем через левый факторинг становится
E -> 'a' | ε
Замена
Подстановка правила в другое правило для устранения косвенных конфликтов или конфликтов FIRST / FOLLOW. Обратите внимание, что это может вызвать конфликт ПЕРВЫЙ / ПЕРВЫЙ.
Для общего метода см. Удаление левой рекурсии . Простой пример удаления левой рекурсии: Следующее производственное правило оставило рекурсию на E
E -> T
Это правило представляет собой не что иное, как список Ts, разделенных знаком «+». В форме регулярного выражения T ('+' T) *. Так что правило можно переписать как
Z -> '+' T Z
Z -> ε
Теперь нет левой рекурсии и конфликтов ни по одному из правил.
Однако не все контекстно-свободные грамматики имеют эквивалентную LL (k) -грамматику, например:
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε
Можно показать, что не существует никакой LL (k) -грамматики, принимающей язык, порожденный этой грамматикой.
Сравнение генераторов парсеров
Дерево синтаксического анализа
Анализ сверху вниз
Анализ снизу вверх
Ноты
^
Розенкранц, диджей; Стернс, Р. Э. (1970). «Свойства детерминированных грамматик сверху вниз» . Информация и контроль . 17 (3): 226–256. DOI : 10.1016 / s0019-9958 (70) 90446-8 .
^ Jarzabek Станислав; Кравчик, Томаш (1974). ""LL-регулярные грамматики"". Instytutu Maszyn Matematycznych : 107–119.
^ Jarzabek Станислав; Кравчик, Томаш (ноябрь 1975 г.). ""LL-регулярные грамматики"" . Письма об обработке информации . 4 (2): 31–37. DOI : 10.1016 / 0020-0190 (75) 90009-5 .
^ Дэвид А. Поплавский (август 1977). Свойства LL-регулярных языков (технический отчет). Университет Пердью , факультет компьютерных наук.
^ Парр, Теренс и Фишер, Кэтлин (2011). «LL (*) основа генератора парсеров ANTLR». Уведомления ACM SIGPLAN . 46 (6): 425–436. DOI : 10.1145 / 1993316.1993548 . CS1 maint: несколько имен: список авторов ( ссылка )
^ Belcak, Питер (2020). «Стратегия анализа LL (конечного) для оптимального анализа LL (k)». arXiv : 2010.07874 [ cs.PL ].
^ Форд, Брайан (2004). «Анализ грамматик выражений: основанная на распознавании синтаксическая основа». Уведомления ACM SIGPLAN . DOI : 10.1145 / 982962.964011 .
↑ Пэт Терри (2005). Компиляция с C # и Java . Pearson Education. С. 159–164. ISBN 9780321263605 .
^ Уильям М. Уэйт и Герхард Гус (1984). Конструкция компилятора . Тексты и монографии по информатике. Гейдельберг: Springer. ISBN 978-3-540-90821-0 . Здесь: разд. 5.3.2, п. 121-127; в частности, стр. 123.
^ Ричард Э. Стернс и П. М. Льюис (1969). «Грамматики свойств и настольные машины» . Информация и контроль . 14 (6): 524–549. DOI : 10.1016 / S0019-9958 (69) 90312-X .
^ «Архивная копия» (PDF) . Архивировано (PDF) из оригинала 18.06.2010 . Проверено 11 мая 2010 . CS1 maint: заархивированная копия как заголовок ( ссылка )
^ Современный дизайн компилятора , Grune, Bal, Jacobs и Langendoen
внешние ссылки
Учебник по реализации парсеров LL (1) на C # (в архиве)
Симулятор синтаксического анализа Этот тренажер используется для создания таблиц синтаксического анализа LL (1) и для решения упражнений книги.
LL (1) DSL PEG parser (инструментарий)
Теоретико-языковое сравнение грамматик LL и LR
LL (k) Теория синтаксического анализа
