Build Parse Baum mit Prolog

Question

Ich versuche Parser mit Prolog zu schreiben. Ich habe meine Tokenizer, die Liste der Token zurückgibt. Zum Beispiel: Tokens = [key(read),id('N'),sep(:=),int(10),....] Alles, was ich brauche, ist Prolog zu machen, um den Befehl zum Ausführen eines Programms zurückzugeben.

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

Die Frage ist, was einfachste Weg ist, Parse-Baum für gegebene Token und Grammatik (wie bison) zu bauen. Ich wäre dankbar für jede Hilfe.

Answer 1

Wenn Sie dem Vorschlag von @mat folgen und Ihre Syntax für einen Token-Stream verwenden, hier ein einfaches Beispiel.

Angenommen, Sie die folgende BNF Definition Ihrer Sprache haben:

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

Sie entscheiden müssen, wie Sie Ihren Parse-Baum darstellen wollen. Ich habe gewählt, was eine klobige Art zu sein scheint, den n-stufigen Syntaxbaum als eingebettete Listen darzustellen (ich habe nicht viel darüber nachgedacht), aber hoffentlich gibt Ihnen das die Idee, wie es funktioniert. Ihre DCG würde die BNF direkt reflektieren, und das Argument wäre der Parsing-Baum:

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) --> ... 

Sie telefonisch vom DCG mit dem Token-Stream analysieren würde:

phrase(program(ParseTree), TokenStream). 

Ein Programm Parse-Baum aussehen würde, :

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

Jeder StatementN_List würde sich ein n-ary Baum für die Anweisung Teilstruktur sein.