使用 prolog 构建解析树

Question

我正在尝试使用 prolog 编写解析器。我有我的分词器，其中 returns 分词列表。例如： Tokens = [key(read),id('N'),sep(:=),int(10),....] 我只需要为 return 指令集制作运行程序的序言。

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

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

Answer 1

跟进@mat 的建议，并使用您的令牌流语法，这是一个简单的示例。

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

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

您需要决定如何表示您的解析树。我选择了一种看起来笨拙的方法来将 n 元解析树表示为嵌入式列表（我没有花很多心思），但希望这会让您了解它是如何工作的。您的 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 叉树。

使用 prolog 构建解析树

Build parse tree with prolog

parsing

prolog

bison

tokenize

dcg