Как / будет работать следующий фрагмент кода для генерации AST? - PullRequest
Новая
       37

Как / будет работать следующий фрагмент кода для генерации AST?

1 голос
/ 13 апреля 2011

Мы пишем компилятор для класса компиляторов Al Aho, и мы рассматриваем следующий код для генерации нашего AST. Вот немного фона. Мы хотим реализовать правила области видимости в виде стека сопоставлений имен и идентификаторов и хотим поместить набор сопоставлений в стек, прежде чем мы войдем и сгенерируем узлы для объявлений. 

compound_statement : {pushScope();} statement_list {popScope();}

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

Ответы [ 2 ]

1 голос
/ 13 апреля 2011

Ваш вопрос говорит о построении узлов AST, но основная часть вашего объяснения говорит о таблицах символов. Эти идеи не совпадают! AST представляет структуру программы. Таблицы символов представляют собой выводы о том, какие имена видны, где и какие типы у них есть.

После того, как вы сфокусировались на таблице символов, ваше представление о том, что вы нажимаете текущую область, когда вы «входите» в блок, и выталкиваете его, когда вы «выходите», концептуально верно, поскольку оно абстрактно достигает новой области видимости для блока.

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

  compound_statement : block_start statement_list block_end ;
  block_start = '{' pushScope() ;
  block_end = '}' popScope();

Я добавил действия, чтобы блокировать начало и конец симметрично, но вы можете быть немного более экономными (улыбка): 

  compound_statement : block_start statement_list '}' popScope() ;
  block_start = '{' pushScope() ;

Настоящим секретом здесь было создание возможности выполнения редукции / семантического действия после входа в блок путем добавления подправила к исходному правилу. Я часто делал это, используя пустое правило: 

  compound_statement : '{' compound_statement_sub_rule block_start statement_list '}' popScope() ;
  compound_statement_sub_rule = pushScope() ;

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

Я бы пошел в рабочее время и задавал столько вопросов, сколько вы можете вспомнить, думали ли вы, что они глупые или нет. Это окупится щедро.

0 голосов
/ 13 апреля 2011

Когда вы вставляете действие в «середину» правила в yacc, оно фактически создает новый скрытый нетерминал для действия и выполняет правило, когда скрытый нетерминал уменьшается. Итак, ваше правило: 

compound_statement : {pushScope();} statement_list {popScope();} ;

эквивалентно: 

compound_statement : hidden_rule statement_list {popScope();} ;
hidden_rule : {pushScope();} ;

с добавлением, что yacc будет корректно изменять ссылки $ n в действии, чтобы они ссылались на правильные вещи.

Таким образом, pushScope будет выполняться при уменьшении hidden_rule (что происходит до уменьшения любого оператора в statement_list), в то время как popScope выполняется после того, как все операторы уменьшены, так что на самом деле это будет делать именно то, что вы хотите.

...