2016-05-04 28 views
3

私はプロローグを使ってパーサに書き込もうとしています。 私は、トークンのリストを返すトークナイザを持っています。例: Tokens = [key(read),id('N'),sep(:=),int(10),....]私が必要とするのは、プログラムを実行するための命令セットを返すためにプロローグを作成することだけです。プロローグで構文木を構築する

program = []. 
program = [Instructions | Program]. 

質問は(bisonのように)与えられたトークンと文法のための解析ツリーを構築するための最も簡単な方法は何か、です。私はどんな助けにも感謝しています。

+3

[タグ:dcg]を参照してください。純粋なプロローグの関係は、*すべての方向*で使用できます。つまり、リストとその解析木の間の関係を記述すると、リストとツリーの両方を解析する**と**を生成することができます。抽象構文ツリーとトークンのリストの間の関係を記述する 'program(AST) - > ...'のようなDCGルールから始めましょう。 – mat

答えて

2

@matの提案をフォローアップし、トークンストリーム用の構文を使用すると、ここに簡単な例があります。

はあなたの言語を定義し、次のBNFがあるとします。

<program> ::= program begin <statement_list> end . 
<statement_list> ::= <statement> | <statement> ; <statement_list> 
<statement> ::= ... 

あなたはあなたのパースツリーを表現する方法を決定する必要があります。私は組み込みリストとしてn-ary構文木を表現するのにぎこちない方法のように思っていましたが(私はそれに多くのことを考えませんでした)、うまくいけば、それがどのように動作するのかを知ることができます。あなたのDCGは直接BNFを反映することになる、との引数は、解析ツリーのようになります。

program([key(program), key(begin), AST_statement_list, key(end), sep(.)]) --> 
    [key(program), key(begin)], 
    statement_list(AST_statement), 
    [key(end), sep(.)]. 

statement_list([AST]) --> statement(AST). 
statement_list([AST_statement | AST_statement_list]) --> 
    statement(AST_statement), 
    statement_list(AST_statement_list). 

statement(AST) --> ... 

あなたはトークンストリームであなたのDCGを呼び出すことによって解析します:

phrase(program(ParseTree), TokenStream). 

プログラム解析ツリーは次のようになります:

[key(program), key(begin), [Statement1_List, Statement2_List, ...], key(end), sep(.)] 

は各StatementN_Listは、それ自体が文のサブツリーのためのn分木になります。