Абстрактное синтаксическое дерево в компиляторе: как точно представлять функцию?

Question

Мы создаем очень простой язык программирования, используя Flex и Bison для анализа синтаксиса и синтаксиса, а также с помощью C для создания компилятора. Прежде чем перейти к сборке, мы создаем абстрактное синтаксическое дерево из языковых правил. Но у нас возникают проблемы с представлением одной конкретной функции с языка. функция описывается следующим образом:

FILTERC: Он принимает условие и список выражений в качестве входных данных и возвращает сколько из этих выражений соответствует условию. Это может быть одиночное или компромиссное условие. Используется в этой форме: FILTERC (условие, [список выражений]) Условие должно иметь знак подчеркивания перед каждым элементом, представляющий, где выражения должны быть помещены для сравнения. Пример: FILTERC (_> 4 и _ < = 6,5, [а + с, Ь, ча, д])

Это, как функция "filterc" выражается в правилах BNF (мы на самом деле использовали лексемы с Flex, но я упростил его с реальными персонажами, так что это не точка, а анализ синтаксиса правильно сделано Bison):

filter ::= FILTERC (condition_filter , [ expression_list ]) 
; 
condition_filter ::= comparison_filter | comparison_filter AND comparison_filter | comparison_filter OR comparison_filter 
; 
comparison_filter ::= _ > expression | _ < expression | _ == expression | _ >= expression | _ <= expression | _ != expression 
; 
expression_list ::= expression | expression , expression_list 
; 
expression: term | expression + term | expression - term 
; 
term: factor | term * factor | term/factor 
; 
factor: ID | INT_LITERAL | REAL_LITERAL | STRING_LITERAL | (expression) | filter 
; 

Теперь мы должны написать функции, которые создают узлы абстрактного синтаксического дерева , На низком уровне функция «filterc» - это не что иное, как куча «IF», ​​чтобы убедиться, что каждое из выражений соответствует условию, только теперь выражения будут помещены там, где подчеркивается. Таким образом, это было бы примерно так: (выражение) (оператор сравнения) (условие)

Дело в том, что фактическое предложение FILTERC считывается «назад»: сначала выражения считываются, а затем сравниваются с условием. Но программа читается последовательно: подчеркивание читается до того, как будет найдено фактическое выражение. Поэтому мы действительно запутались в том, как построить дерево.

Я не собираюсь добавлять весь код, который мы используем для создания узлов и листьев дерева, или это было бы полным беспорядком. Но в основном есть функция, которая создает узлы с двумя дочерними элементами (слева и справа), и когда не должно быть никаких детей, эти указатели имеют значение null. Основная структура, которую мы используем, заключается в том, чтобы поместить оператора в корневой узел и операнды в качестве дочерних элементов (например: в предложении «if» ключевым словом «if» должен быть корень, условием будет левый ребенок и код блок для выполнения, если true будет правильным потомком). Например:

IF condition THEN block {thenPtr = blockPtr;} ENDIF {createNode("if", conditionPtr, thenPtr);} 

(«условие» и «блок» определены в другом месте, где создаются их указатели).

Мы смогли успешно создать дерево для выражения regex и для всех других правил на этом языке, но эта функция «фильтр» действительно запутанна.

Answer 1

Это правда, что когда анализатор считывает фрагмент выражения (например, «>»), ему не хватает достаточно, чтобы построить дерево для выражения. То же самое верно для любой концепции («нетерминальной») на вашем языке. И с этой точки зрения я вижу вас, вы можете быть смущены.

Видимо, вы не понимаете, как работают парные анализаторы LR, такие как Bison. Предположим, что у нас есть правила R1, R2, ... с правилами имеют правые стороны, например Rn = T1 T2 T3; причем каждое правило имеет длину правой стороны L (Rn).

Основная идея, что вам нужно, это то, что парсер LR собирает («стеки», да он действительно использует стек токенов) из входного потока слева направо. Эти шаги называются «сдвигами». Парсер сменяет многократно, постоянно ищет ситуации, которые указывают, что было прочитано достаточно токенов (например, T1, T2, затем T3), чтобы удовлетворить правую часть некоторого правила грамматики Rn. Магия генератора парсера и создаваемые ею таблицы LR позволяют парсеру эффективно отслеживать все «живые» правила сразу, и мы не будем обсуждать это дальше.

В точке, где в этой точке была распознана правая сторона, парсер LR выполняет действие «уменьшить» и заменяет сложенные токены, соответствующие телу правила, с нетерминальным токеном Rn («pops» стек L (Rn) раз тогда и толкает Rn "). Он делает столько сокращений, сколько может, перед возвратом к сбору терминальных токенов из входного потока. Стоит вашей проблемы, чтобы имитировать этот процесс вручную на действительно крошечной грамматике. [Тонкая деталь: некоторые правила имеют пустые правые стороны, например, L (Rn) == 0); в этом случае, когда происходит уменьшение ноль появляются попсы, да, это звучит смешно, но это смертельно правильно].

В любой момент, когда парсер выполняет действие по сокращению, он предлагает вам, программирующему синтаксическому анализатору, возможность выполнить дополнительную работу. Эта дополнительная работа почти всегда является «деревом». Ясно, что все маркеры, которые составляют правило Rn, все видели, поэтому можно построить дерево, представляющее Rn, если токены были всеми терминалами. Фактически, если все маркеры для Rn были замечены, а Rn содержит некоторые нетерминалы, тогда должны были быть уменьшены действия для создания каждого из нетерминалов. Если каждый из их создал дерево, представляющее себя, то при сокращении правила, содержащего нетерминал, для других нетерминалов уже созданы деревья, и их можно объединить для создания дерева для текущего правила.

Инструменты генератора парсеров LR, такие как Bison, помогут вам, как правило, предоставляя операторам по дереву, которые вы можете использовать при уменьшении действия. Это также помогает сделать деревья для уже обработанных нетерминалов доступными для вашего сокращения действия, поэтому он может комбинировать их для создания дерева для действия уменьшения. (Это делается путем отслеживания генерируемых деревьев в стеке, параллельных стеке токенов.) Ни в коем случае не пытайтесь уменьшить или пытаетесь создать дерево, где у вас нет всех необходимых поддеревьев ,

Я думаю, вам нужно внимательно прочитать Bison вручную , и все это станет ясным, поскольку вы пытаетесь реализовать парсер и сокращения; у руководства есть хорошие примеры. Ясно, что вы этого не сделали (боязнь не знать, как обращаться с деревьями?), Потому что: а) ваши правила, выраженные, нарушены; нет способа генерировать термин, и б) у вас нет встроенных действий уменьшения.