关于 LL1 非递归解析器中的 AST 构造 [英] About AST construction in LL1 non recursive parser

问题描述

我已经使用显式堆栈以非递归方法实现了一个 LL1 解析器.

I have implemented a LL1 parser in a non recursive approach with a explicit stack.

以下算法来自龙书:

set zp to point to the first symbol of w;
set X to the top stack symbol;
while ( X != $ ) { /* stack is not empty */
    if ( X is a ) 
       pop the stack and advance zp;
    else if ( X is a terminal )
       error();
    else if ( M[X, a] is an error entry )
       error();
    else if ( M[X,a] = X -+ Y1Y2 Yk ) {
       output the production X -+ YlY2 - . Yk;
       pop the stack;
       push Yk, Yk-1,. . . , Yl onto the stack, with Yl on top;

    set X to the top stack symbol;
}

书中说:

解析器由一个程序控制，该程序考虑 X，即栈顶，a，当前输入符号.如果 X 是非终结符，解析器通过咨询条目选择一个 X 产品解析表 IM 的 M[X, a].(可以执行额外的代码例如，这里是在解析树中构造节点的代码.)否则，它检查终端 X 和当前的匹配输入符号a.

The parser is controlled by a program that considers X, the symbol on top of the stack, and a, the current input symbol. If X is a nonterminal, the parser chooses an X-production by consulting entry M[X, a] of the parsing table IM. (Additional code could be executed here, for example, code to construct a node in a parse tree.) Otherwise, it checks for a match between the terminal X and current input symbol a.

但是我需要更多关于如何在这种方法下构建表达式树节点的信息.我有一个 UnaryOperator、BinaryOperator 等节点层次结构，但不知道在哪里实例化它.

However i need more info on how to construct the expression tree nodes under this approach. I have a node hierarchy of UnaryOperator, BinaryOperator, etc but dont know where to instanciate it.

然而，我还没有找到任何简单的例子(例如算术语言).

Yet i havent found any simple example of this (with for example the arithmetic language).

推荐答案

我一直在寻找相同的信息 - 如何使用 LL(1) 表驱动的非递归解析创建解析树 - 并找到了很少.

I have been searching a while for the same information - how to create a parse tree with an LL(1) table-driven non-recursive parse - and found very little.

刚才我找到了这些讲义https://parasol.tamu.edu/~rwerger/Courses/434/lec7.pdf 其中提出，对于每个终结符或非终结符，相应的解析树节点也被压入堆栈.不过，不知何故，它确实看起来很浪费.这是伪代码中提出的算法:

Just now I found these lecture notes https://parasol.tamu.edu/~rwerger/Courses/434/lec7.pdf in which it is proposed that for every terminal or nonterminal, the corresponding parse tree node is also pushed onto the stack. It does seem wasteful somehow, though. Here is the proposed algorithm in pseudocode:

TOS ← 0
Stack[tos++] ← eof
Stack[tos++] ← *root node*
Stack[tos++] ← *Start Symbol*
token ← next_token()
X ← Stack[tos]
repeat
  if X is a terminal or eof then
    if X = token then
      pop X
      token ← next_token()
      *pop and fill in node*
    else error()
  else /* X is a non-terminal */
    if M[X,token] = X → Y1Y2...Yk then
      pop X
      *pop node for X
      build node for each child and
      make it a child of node for X*
      push nk,Yk,nk-1,Yk-1...n1,Y1
    else error()
until X = eof

这篇关于关于 LL1 非递归解析器中的 AST 构造的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！