Я недавно закончил свой первый анализатор / компилятор для специального языка программирования. У меня была некоторая свобода в спецификации этого языка, и в некоторых местах я изменил спецификацию, чтобы было легче разобрать; что в некоторых местах привело к некоторым (пока) незначительным улучшениям в самом языке. Может быть, я исправлю это в будущем v2; на данный момент я все еще перевариваю то, что узнал из этого процесса, и у меня есть несколько вопросов по этому поводу. Я никогда не проходил формальный курс по проектированию компиляторов, поэтому хочу убедиться, что мое понимание соответствует современному уровню в этой области.
В большинстве статей и учебников процесс разбора разбивается на два этапа: токенизация и лексический анализ. Затем обычно упоминается, что в большинстве реальных реализаций они обычно несколько взаимосвязаны, чтобы сделать реализацию проще. Мой собственный опыт был противоположным: смешивание их усложняло ситуацию, и я даже добавил третий проход. Я делаю первый проход, в котором я делаю минималистический токенинг, под которым я подразумеваю, что я определяю «токен» в его наиболее простой форме. Я экспериментировал с подходами, в которых, например, конструктор в целом был «токеном». Я отошел от этого подхода и теперь называю только «токены» вещами, которые являются основными строительными блоками программы. Затем я делаю лексический анализ, в котором я строю AST. Тогда мой третий проход - это (то, что я называю) структурный анализ, в котором я делаю, например, проверка типа, проверьте, соответствует ли количество аргументов, передаваемых функциям, сигнатурам этих функций и т. д. Не является ли это обычно частью «разбора», или не помещено в «лексический анализ», или почему литература предлагает в основном два пройти разбор подходов? (возможно, у меня есть четвертый проход, генерация кода, но это в основном отдельный процесс).
Мой лексер является (я думаю) рекурсивным спуском - у меня есть подпрограммы, которые соответствуют потокам токенов или возвращают false, когда они не могут, и затем пытаются сопоставить другое «правило», вплоть до обработки всех токенов , Эти подпрограммы рассчитывают максимум на 2 токена; насколько я понимаю, это означает, что у меня есть «LL (2) грамматика». Мой вопрос: какое значение имеет это число? Являются ли «LL (1) грамматики» как-то «лучше», чем грамматики с большим числом? Кроме того, почему возврат нежелателен? (или нет, и я просто неправильно понимаю?)
Почему классификация грамматик так важна? Все тексты начинаются с (как правило, довольно обширного) их объяснения, но, насколько я понимаю, вы не сможете реально изменить свойства грамматики, не внеся изменений в работу языка, который вы разрабатываете. Теперь я понимаю, что если вы хотите проанализировать существующий язык, классификация его структуры позволит вам доказать класс сложности результирующего синтаксического анализатора; но при разработке нового языка (imo) самое важное - это выразительность или другой вид соответствия поставленной цели, а производительность синтаксического анализатора для него имеет второстепенное значение. Хотя я понимаю, что эта последняя часть является дискуссионной, существуют ли практические причины при разработке нового языка внимательно следить за типом грамматики?