8

私は現在パーサーを手作業で構築しています。LL(1) パーサーです。現時点では、それは優れた認識機能です。その関数 parse(List tokens) は、tokens が言語のメンバーであるかどうかを決定します。

ここで、その入力に対応する AST を構築したいと思います。ただし、再帰的な降下方法で実装する方法を知っています（すでに実行しています）。つまり、課題として、従来のアルゴリズムのスタックを使用してスタックを実装します。

next <- first token of the input
stack <- START_SYMBOL
do {
    top <- stack.pop()
    if (top is a terminal and top == next) {
        next <- next token of the input
    } else if (top is a non terminal and PARSING_TABLE[top, next] exists) {
        stack.push(PARSING_TABLE[top, next]);
    } else {
         return invalid input;
    }
} while (stack is not empty);
return valid input;

ここで、PARSING_TABLE は LL(1) テーブルです。しかし、そのような構成で AST をビルドする部分をどのように実装するのだろうか。私は完全な実装を求めるのではなく、実装のアイデアを求めます。

ありがとう ！

4

2 に答える 2

2

AST エントリ参照 (つまり、ルール番号 + ルール内の位置 + 格納先のターゲット データ) + (ターミナル/非ターミナル) が含まれるように、スタックに注釈を付けることができます。

その結果をASTinitial stack <- START_SYMBOLルートに格納するように注釈が付けられています。

基本的に、pop()現在の AST コンストラクトを選択します。次に、next <- next token値を AST に保存します。はstack.push(PARSING_TABLE[top, next]);新しい AST リストを開き、それを に対応する構造に書き込みtop、スタックの各エントリに「ルール番号 + 位置 + ターゲット リスト」を生成します。

解析が完了すると、ツリー全体ができあがります。

厳密な AST では、いくつかのトークンを無視したい場合があります。これは、push() 部分で設定されたスタック内の適切な注釈を介して行うことができます。典型的な方法は、各ルール (A -> BC) にメタ情報を付加することです。たとえば、何を保持するか、結果の性質は何かなどです。

于 2013-11-26T10:59:05.777 に答える
1

スタック上の非終端記号を一致規則の rhs に置き換える一般的な方法では、予測された時点で文法構造を事実上忘れてしまうため、問題が発生します。ただし、AST を生成するには、後でルール解析が完了したときにその構造が必要になります。

非終端記号を一致ルールの rhs 記号に置き換えるのではなく、そのままにして、一致した記号をリスト オブジェクトとしてプッシュします。このようにして、スタックは文法の階層構造を保持します。

解析は、一番上のリストのシンボルを消費します。リストの枯渇は、ルールの完了に対応します。非終端記号は、予測されたときではなく、ルールが完了したときにスタックから削除されます。

スタックが消費されると、関連するルールを記憶し、解析されたトークンを格納する必然的な AST 構造を構築します。したがって、スタックは、解析された AST に流れ込む予測された AST のように機能します。

これは、呼び出しフレームのスタックとしてシンボル リストのスタックを使用して、再帰降下パーサーの呼び出し階層をエミュレートしていると考えることができます。

ルビーで：

# g is the grammar; a list of rules
# s is a terminal sequence to parse
# note, this code does not tokenize EOF

def parse(g, s)

 tab = gen_table(g)
 stack = [[g.start_sym]]
 # intermediate ast node format: [rule-action, symbols...]
 ast = [[->(rhs){[:_S, rhs[0]]}]]

 loop do
  puts "PARSE\n #{s}\n #{stack}\n #{ast}"

  if stack.first.empty?
   raise "extraneous input" if not s.empty?
   break
  end

  if stack.last.empty? # rule complete
   stack.pop
   node = ast.pop
   # transform the node (eg to a class) using the associated rule-action
   node = node.first.(node.drop(1))
   ast.last.push(node)
   stack.last.shift # rm sym from stack after completing it
   next
  end

  raise "incomplete input" if s.empty?
  tok = s.first
  topsym = stack.last.first

  if topsym.is_a? String # terminal
   raise "mismatch #{tok} != #{topsym}" if tok != topsym
   stack.last.shift
   ast.last.push(s.shift)

  elsif topsym.is_a? Symbol # nonterminal
   ri = tab[topsym][tok]
   raise "no rule for #{topsym}, #{tok}" if ri.nil?
   stack.push(g[ri].rhs.clone)
   ast.push([g[ri].action])
  end

 end

 node = ast.first
 node.first.(node.drop(1))
end
于 2015-08-08T08:02:43.110 に答える