Здесь много ответов, но они все путают. Да, есть парсеры LL и LR, но это не ваш выбор.
У вас есть грамматика. Существуют инструменты, которые автоматически создают парсер для вас по заданной грамматике. Почтенные Yacc и Бизон сделайте это. Они создают парсер LR (на самом деле LALR). Существуют также инструменты, которые создают для вас парсер LL, например ANTLR. Недостатком подобных инструментов является их негибкость. Их автоматически генерируемые сообщения об ошибках синтаксиса отстой, восстановление ошибок затруднено, а более старые побуждают вас учитывать ваш код одним способом, который оказывается неправильным. Правильный способ - заставить ваш синтаксический анализатор выдать абстрактное синтаксическое дерево, а затем заставить компилятор сгенерировать код из него. Инструменты хотят, чтобы вы смешивали код парсера и компилятора.
Когда вы используете такие автоматизированные инструменты, разница в мощности между LL, LR и LALR действительно имеет значение. Вы не можете «обмануть», чтобы расширить их силу. (Мощность в данном случае означает способность генерировать синтаксический анализатор для действительной контекстно-свободной грамматики. Допустимая контекстно-свободная грамматика — это та, которая генерирует уникальное правильное дерево синтаксического анализа для каждого ввода или правильно говорит, что не соответствует грамматике.) Мы в настоящее время нет генератора синтаксических анализаторов, который может создать синтаксический анализатор для каждой допустимой грамматики. Однако LR может обрабатывать больше грамматик, чем любой другой вид. Неспособность обрабатывать грамматику не является катастрофой, поскольку вы можете переписать грамматику в форме, которую может принять генератор синтаксического анализатора. Однако не всегда очевидно, как это должно быть сделано, и, что еще хуже, это влияет на сгенерированное абстрактное синтаксическое дерево, что означает, что слабые места в синтаксическом анализаторе распространяются на остальную часть вашего кода - как и компилятор.
Причина существования синтаксических анализаторов LL, LALR и LR заключается в том, что работа по созданию синтаксического анализатора LR требовала от современного компьютера больших затрат времени и памяти. (Обратите внимание, что для этого требуется сгенерировать парсер, что происходит только тогда, когда вы его пишете. Сгенерированный парсер работает очень быстро.) Но это было очень давно. Генерация синтаксического анализатора LR(1) занимает гораздо меньше 1 ГБ ОЗУ для умеренно сложного языка, а на современном компьютере — меньше секунды. По этой причине лучше использовать автоматический генератор синтаксических анализаторов LR, например Hyacc.
Другой вариант - вы пишете свой собственный парсер. В этом случае есть только один выбор: синтаксический анализатор LL. Когда люди здесь говорят, что писать LR сложно, они преуменьшают значение. Человеку практически невозможно вручную создать синтаксический анализатор LR. Вы можете подумать, что это означает, что если вы пишете свой собственный синтаксический анализатор, вы вынуждены использовать грамматики LL(1). Но это не совсем так. Поскольку вы пишете код, вы можете обманывать. Вы можете смотреть вперед произвольное количество символов, и поскольку вам не нужно ничего выводить, пока вы не будете готовы, абстрактное синтаксическое дерево не должно соответствовать используемой вами грамматике. Эта способность обманывать компенсирует всю утраченную силу между LL и LR(1), а часто и часть.
У рукописных парсеров, конечно, есть свои недостатки. Нет никакой гарантии, что ваш синтаксический анализатор действительно соответствует вашей грамматике, или, если уж на то пошло, нет проверки правильности вашей грамматики (т.е. распознает язык, который, по вашему мнению, он делает). Они длиннее и еще хуже побуждают вас смешивать код разбора с кодом компиляции. Кроме того, очевидно, что они реализованы только на одном языке, в то время как генератор синтаксических анализаторов часто выдает результаты на нескольких разных языках. Даже если это не так, таблица синтаксического анализа LR может быть представлена в виде структуры данных, содержащей только константы (скажем, в формате JSON), а фактический синтаксический анализатор состоит всего из 100 строк кода или около того. Но есть и положительные стороны написанного от руки парсера. Поскольку вы написали код, вы знаете, что происходит, поэтому легче выполнять восстановление после ошибок и генерировать разумные сообщения об ошибках.
В конце концов, компромисс часто работает следующим образом:
- Для разовых заданий лучше использовать генератор синтаксических анализаторов LR(1). Генератор проверит вашу грамматику, избавит вас от работы, а современные генераторы напрямую разбивают абстрактное синтаксическое дерево, а это именно то, что вам нужно.
- Для хорошо отполированных инструментов, таких как mcc или gcc, используйте написанный от руки анализатор LL. Вы все равно будете писать множество модульных тестов, чтобы защитить свою спину, восстановление после ошибок и сообщения об ошибках намного проще исправить, и они могут распознавать более широкий класс языков.
Единственный другой вопрос, который у меня есть: почему C? Компиляторы обычно не являются критичным ко времени кодом. Существуют очень хорошие пакеты синтаксического анализа, которые позволят вам выполнить работу за половину кода, если вы хотите, чтобы ваш компилятор работал немного медленнее — мой собственный Lrparsing, например. Имейте в виду, что «немного медленнее» здесь означает «едва заметное для человека». Я предполагаю, что ответ таков: «задание, над которым я работаю, указывает C». Чтобы дать вам представление, вот насколько простым становится переход от вашей грамматики к дереву синтаксического анализа, когда вы ослабляете требование. Эта программа:
#!/usr/bin/python
from lrparsing import *
class G(Grammar):
Exp = Ref("Exp")
int = Token(re='[0-9]+')
id = Token(re='[a-zA-Z][a-zA-Z0-9_]*')
ActArgs = List(Exp, ',', 1)
FunCall = id + '(' + Opt(ActArgs) + ')'
Exp = Prio(
id | int | Tokens("[]", "False True") | Token('(') + List(THIS, ',', 1, 2) + ')' |
Token("! -") + THIS,
THIS << Tokens("* / %") << THIS,
THIS << Tokens("+ -") << THIS,
THIS << Tokens("== < > <= >= !=") << THIS,
THIS << Tokens("&&") << THIS,
THIS << Tokens("||") << THIS,
THIS << Tokens(":") << THIS)
Type = (
Tokens("", "Int Bool") |
Token('(') + THIS + ',' + THIS + ')' |
Token('[') + THIS + ']')
Stmt = (
Token('{') + THIS * Many + '}' |
Keyword("if") + '(' + Exp + ')' << THIS + Opt(Keyword('else') + THIS) |
Keyword("while") + '(' + Exp + ')' + THIS |
id + '=' + Exp + ';' |
FunCall + ';' |
Keyword('return') + Opt(Exp) + ';')
FArgs = List(Type + id, ',', 1)
RetType = Type | Keyword('void')
VarDecl = Type + id + '=' + Exp + ';'
FunDecl = (
RetType + id + '(' + Opt(FArgs) + ')' +
'{' + VarDecl * Many + Stmt * Some + '}')
Decl = VarDecl | FunDecl
Prog = Decl * Some
COMMENTS = Token(re="/[*](?:[^*]|[*][^/])*[*]/") | Token(re="//[^\n\r]*")
START = Prog
EXAMPLE = """\
Int factorial(Int n) {
Int result = 1;
while (n > 1) {
result = result * n;
n = n - 1;
}
return result;
}
"""
parse_tree = G.parse(EXAMPLE)
print G.repr_parse_tree(parse_tree)
Производит этот вывод:
(START (Prog (Decl (FunDecl
(RetType (Type 'Int'))
(id 'factorial') '('
(FArgs
(Type 'Int')
(id 'n')) ')' '{'
(VarDecl
(Type 'Int')
(id 'result') '='
(Exp (int '1')) ';')
(Stmt 'while' '('
(Exp
(Exp (id 'n')) '>'
(Exp (int '1'))) ')'
(Stmt '{'
(Stmt
(id 'result') '='
(Exp
(Exp (id 'result')) '*'
(Exp (id 'n'))) ';')
(Stmt
(id 'n') '='
(Exp
(Exp (id 'n')) '-'
(Exp (int '1'))) ';') '}'))
(Stmt 'return'
(Exp (id 'result')) ';') '}'))))
04.05.2013
