Общий синтаксический анализатор языка как конечный автомат

Question

Я написал очень малоэффективный анализатор рекурсивного спуска для общего языка (с открытым исходным кодом, для 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).

Поэтому у меня есть следующие вопросы:

1. Может ли этот подход дает положительные результаты?

2. Имеет ли это некоторые отношения с LL, LR и другими синтаксическими анализаторами? На данный момент у меня недостаточно понимания этих алгоритмов, я не пробовал ни одного из них.

3. Какой алгоритм синтаксического анализа является более быстрым для правильной входной строки? Меня интересует только синтаксический анализ правильных входных строк, потому что я создаю инструмент генерации кода для использования с IDE, который может сообщать о самих ошибках. Поэтому мне нужен самый быстрый алгоритм для этой конкретной задачи.

Спасибо.

UPD:

Я закончил с ANTLRv4, я нашел цель и выполнения для моего языка (Swift), и я более чем доволен.

Answer 1

LALR (k) - O (N) и может быть молниеносно, если вы уменьшите его до машинного кода для «разветвления на токене в состоянии до следующего состояния, соедините значение токена». Неясно, что вы получите, пытаясь развить свою идею; как бы это было быстрее?

[Что имеет значение, самое большее не разбор; это обычно скорость, с которой вы можете создавать лексемы, особенно. устраняя пустое пространство].

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

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

Просто убедитесь, что знаете, к какой цели вы пытаетесь достичь.