parsing - 使用 prolog 构建解析树

Question

我正在尝试使用序言编写解析器。我有我的标记生成器，它返回标记列表。例如:Tokens = [key(read),id('N'),sep(:=),int(10),....] 我需要的只是让 prolog 返回指令集运行程序。

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

问题是，为给定的标记和语法(例如 bison)构建解析树的最简单方法是什么。如果有任何帮助，我将不胜感激。

Answer 1

按照 @mat 的建议，并使用 token 流的语法，这是一个简单的示例。

假设您有以下 BNF 定义您的语言:

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

您需要决定如何表示解析树。我选择了一种看似笨拙的方式来将 n 元解析树表示为嵌入列表(我没有对此进行太多思考)，但希望这能让您了解它是如何工作的。你的 DCG 将直接反射(reflect) 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) --> ...

您可以通过使用 token 流调用 DCG 来进行解析:

phrase(program(ParseTree), TokenStream).

程序解析树看起来像:

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

每个StatementN_List本身就是语句子树的一棵n叉树。