Разбор, какой метод выбрать?
Я работаю над компилятором (язык, близкий к C), и я должен реализовать его на C. Мой главный вопрос - как выбрать правильный метод синтаксического анализа, чтобы быть эффективным при кодировании моего компилятора.
Вот моя текущая грамматика: http://img11.hostingpics.net/pics/273965Capturedcran20130417192526.png
Я думал о создании нисходящего анализатора LL(1), как описано здесь: http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/07-Top-Down-Parsing.pdf
Может ли это быть эффективным выбором, учитывая эту грамматику, зная, что сначала я должен удалить левые рекурсивные правила. Есть ли у вас какие-либо другие советы?
Спасибо, Ментине
4 ответа
Наиболее эффективными синтаксическими анализаторами являются LR-парсеры, а LR-парсеры немного сложны в реализации. Вы можете использовать технику синтаксического анализа рекурсивного спуска, поскольку это проще реализовать в C.
Здесь много ответов, но они все путают. Да, есть парсеры LL и LR, но это не ваш выбор.
У вас есть грамматика. Существуют инструменты, которые автоматически создают парсер для вас с учетом грамматики. Почтенные Як и Бизон делают это. Они создают парсер 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? Компиляторы обычно не являются критичным ко времени кодом. Есть очень хорошие парсинговые пакеты, которые позволят вам выполнить работу в 1/2 кода, если вы хотите, чтобы ваш компилятор работал немного медленнее - например, мой собственный 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')) ';') '}'))))
Самый эффективный способ создания синтаксического анализатора - использовать специальный инструмент, целью которого является создание синтаксического анализатора. Раньше их называли компиляторами, но в настоящее время акцент сместился (расширен) на языковые средства, которые предоставляют вам больше помощи для создания собственного языка. Например, практически любой языковой инструментальные средства предоставят вам поддержку IDE и подсветку синтаксиса для вашего языка, просто взглянув на грамматику. Они также очень помогают в отладке вашей грамматики и вашего языка (вы не ожидали, что левая рекурсия будет самой большой из ваших проблем, не так ли?).
Среди лучших поддерживаемых и развивающихся языковых рабочих мест можно назвать:
Если вы действительно так склонны, или если вы подумываете о том, чтобы написать парсер самостоятельно для развлечения и опыта, лучшими современными алгоритмами являются SGLR, GLL и Packrat. Каждый из них является квинтэссенцией алгоритмических исследований, которые длились полвека, поэтому не ожидайте, что вы поймете их полностью в одно мгновение, и не ожидайте ничего хорошего из первой пары "исправлений", которые вы найдете с. Однако, если у вас получится хорошее улучшение, не стесняйтесь поделиться своими результатами с авторами или опубликовать их иным способом!
Спасибо за все эти советы, но мы наконец решили создать свой собственный парсер рекурсивного спуска, используя точно такой же метод, как здесь: http://www.cs.binghamton.edu/~zdu/parsdemo/recintro.html
Действительно, мы изменили грамматику, чтобы удалить леворекурсивные правила, и поскольку грамматика, которую я показал в моем первом сообщении, не является LL(1), мы использовали наш список токенов (созданный нашим сканером), чтобы продолжить поиск, который в дальнейшем. Похоже, что это работает довольно хорошо.
Теперь у нас есть сборка AST внутри этих рекурсивных функций. Есть ли у вас какие-либо предложения? Подсказки? Большое спасибо.