我正在尝试使用序言编写解析器。
我有我的标记生成器,它返回标记列表。例如:
Tokens = [key(read),id('N'),sep(:=),int(10),....]
我需要的只是让 prolog 返回指令集运行程序。
program = [].
program = [Instructions | Program].
问题是,为给定的标记和语法(例如 bison
)构建解析树的最简单方法是什么。如果有任何帮助,我将不胜感激。
最佳答案
按照 @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叉树。
关于parsing - 使用 prolog 构建解析树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37019198/