Как начать разбор, когда лексер возвращает токен?(Сборка компилятора)

Question

Я пытаюсь собрать компилятор в C для языка, подобного C. Я прямо сейчас написал лексер, который будет читать входной файл и выводить поток токенов. Теперь я понимаю теорию грамматики и знаю, как писать деревья разбора вручную для разных выражений. Но я немного растерялся, связывая это с реальным кодом! Как мне начать процесс разбора, как только я получу токены? Для начала, что должна делать моя программа парсера, когда она получает первый токен? Я знаю, как-то это должно быть устроено как дерево. Но как мне начать? Любая помощь будет отличной, я только начинающий.

Большое спасибо!

---

следующий токен после обработки текущего токена. Теперь я планирую начать с предположения, что мой язык полностью состоит из операторов присваивания.
Итак, форма БНФ выглядит примерно так:

< assignment_statement > ::= < destination > := < factor >  
< destination > ::= < identifier >
< identifier > ::= [a-zA-Z][a-zA-Z0-9]*
<factor > ::= < name >|< number >|< string >
< name > ::= < identifier >
< number > ::= [0-9]+
< string > ::="[a-zA-Z0-9]*"

Теперь, когда я увижу такое утверждение, как: var := 9, лексер вернет первый токен как "var", каким будет родительское правило и подчиненные правила? Кроме того, как мне построить дерево разбора для этого оператора?

Большое спасибо!

Answer 1

Обычный шаблон - парсер запрашивает токены. Цикл синтаксического анализатора обычно имеет форму «прочитать следующий токен, определить, что с ним делать, обновить частично проанализированное дерево, повторить», и этого легче достичь, если синтаксический анализатор вызывает сам лексер (вместо третьего фрагмента кода, считываемого из лексер и фидеры для парсера).

Конечно, сердце парсера зависит от алгоритма, который вы используете (рекурсивное снижение, LR ...), но обычно он состоит в определении того, соответствует ли новый токен правилу, которое вы сейчас анализируете (например, поиск - при чтении EXPR = '-' EXPR | ...), соответствует подправилу (например, поиск class при чтении DEF = CLASS | ..., например, CLASS = 'class' ...) или не подходит вообще (с этого момента вы должны прекратить действие текущего правила) , создав соответствующий узел AST и повторив процесс на родительском правиле).

Парсеры рекурсивного спуска делают это с под-вызовами (для подправил) и с возвращаемыми значениями (для возврата к родительскому правилу), в то время как парсеры RL имеют тенденцию объединять несколько правил и подправил в одно и shift , чтобы остаться в текущем наборе правил, или уменьшить , чтобы прекратить действие правил и построить один или несколько узлов AST.