Я написал очень малоэффективный анализатор рекурсивного спуска для общего языка (с открытым исходным кодом, для EBNF-грамматик). И я хочу исправить его производительность, переписывая парсер.Общий синтаксический анализатор языка как конечный автомат
Я читал о лексическом анализе, LL, LR, LALR парсерах и модификациях, таких как LL (*), я прочитал первые 3 главы книги Дракона (о лексерах и парсерах), я изучил проекты с открытым исходным кодом, такие как ANTLR и другие.
И я хочу знать, почему этот алгоритм не описан. Может быть, это неправильно, я не знаю. Или, может быть, я изобрел колесо.
Предположим, что мы имеем грамматику (е: конец файла):
A: B? B 1? e
B: 0 | 1
Грамматика после преобразования:
A: B B 1 e | B B e | B e
B: 0 | 1
Возможные сценарии:
[01] [01] [1] [e]
[01] [01] [e]
[01] [e]
Мы можем построить что-то вроде FSM :
Symbol #0:
[01]: continue
Symbol #1:
[01]: continue
[e]: parse as "B e"
Symbol #2:
[1]: parse as "B B 1 e"
[e]: parse as "B B e"
Он будет анализировать токен потока в точке O (N). Для реальной грамматики он может быть изменен, чтобы быть более чем простым FSM, но все же O (N).
Поэтому у меня есть следующие вопросы:
Может ли этот подход дает положительные результаты?
Имеет ли это некоторые отношения с LL, LR и другими синтаксическими анализаторами? На данный момент у меня недостаточно понимания этих алгоритмов, я не пробовал ни одного из них.
Какой алгоритм синтаксического анализа является более быстрым для правильной входной строки? Меня интересует только синтаксический анализ правильных входных строк, потому что я создаю инструмент генерации кода для использования с IDE, который может сообщать о самих ошибках. Поэтому мне нужен самый быстрый алгоритм для этой конкретной задачи.
Спасибо.
UPD:
Я закончил с ANTLRv4, я нашел цель и выполнения для моего языка (Swift), и я более чем доволен.
Вы забыли 'B 1 e' в своей преобразованной грамматике. Но неясно, о чем вы спрашиваете. Известно, что множество контекстно-свободных языков является надмножеством множества регулярных языков. Вы спрашиваете, как распознать, действительно ли данная грамматика распознает обычный язык? http://stackoverflow.com/questions/559763/regular-vs-context-free-grammars – chepner
Если вы хотите, чтобы кто-то сказал вам, если вы повторно изобретаете алгоритм, попробуйте спросить в отделении Computer Science Stack Exchange , FWIW, анализ LR с использованием состояний машин, обобщенных на автоматические пускатели. –