parsing - 解析器 DCG 不具有确定性是否合适？

Question

我正在为查询引擎编写一个解析器。我的解析器 DCG 查询 不是确定性的。

我将以关系方式使用解析器来检查和综合查询。

解析器 DCG 不具有确定性是否合适？

在代码中:

如果我希望能够以两种方式使用 query/2，是否需要这样做

?- phrase(query, [q,u,e,r,y]).
true;
false.

或者我应该能够获得

?- phrase(query, [q,u,e,r,y]).
true.

尽管如此，鉴于第一个片段需要我这样使用它

?- bagof(X, phrase(query, [q,u,e,r,y]), [true]).
true.

什么时候用它来检查公式？

Answer 1

要问自己的第一个问题是你的语法是确定性的，或者用语法术语来说，unambiguous 。这并不是问你的 DCG 是否是确定性的，而是问语法是否明确。这可以用基本的解析概念来回答，不需要使用 DCG 来回答这个问题。换句话说，是否只有一种方法可以解析有效的输入。这方面的标准书籍是“编译器:原理、技术和工具”( WorldCat )

现在您实际上是在询问解析的三种不同用途。

1. 识别器。
2. 解析器。
3. 发电机。

如果你的语法明确，那么

1. 对于识别器来说，只有对于可解析的有效输入，答案才应为 true，对于无效输入，答案应为 false。
2. 对于解析器来说，它应该是确定性的，因为只有一种方法来解析输入。解析器和识别器之间的区别在于，识别器仅返回 true 或 false，而解析器会返回更多内容，通常是抽象语法树。
3. 对于生成器来说，它应该是半确定性的，以便它可以生成多个结果。

所有这一切都可以用一个 DCG 来完成吗？是的。三种不同的方式取决于您如何使用 DCG 的输入和输出。

<小时/>

这是一个语法非常简单的示例。

语法只是一个带有一个运算符和两个可能的操作数的中缀二进制表达式。运算符为 (+)，操作数为 (1) 或 (2)。

expr(expr(Operand_1,Operator,Operand_2)) -->
    operand(Operand_1),
    operator(Operator),
    operand(Operand_2).

operand(operand(1)) --> "1".
operand(operand(2)) --> "2".

operator(operator(+)) --> "+".

recognizer(Input) :-
    string_codes(Input,Codes),
    DCG = expr(_),
    phrase(DCG,Codes,[]).

parser(Input,Ast) :-
    string_codes(Input,Codes),
    DCG = expr(Ast),
    phrase(DCG,Codes,[]).

generator(Generated) :-
    DCG = expr(_),
    phrase(DCG,Codes,[]),
    string_codes(Generated,Codes).

:- begin_tests(expr).

recognizer_test_case_success("1+1").
recognizer_test_case_success("1+2").
recognizer_test_case_success("2+1").
recognizer_test_case_success("2+2").

test(recognizer,[ forall(recognizer_test_case_success(Input)) ] ) :-
    recognizer(Input).

recognizer_test_case_fail("2+3").

test(recognizer,[ forall(recognizer_test_case_fail(Input)), fail ] ) :-
    recognizer(Input).

parser_test_case_success("1+1",expr(operand(1),operator(+),operand(1))).
parser_test_case_success("1+2",expr(operand(1),operator(+),operand(2))).
parser_test_case_success("2+1",expr(operand(2),operator(+),operand(1))).
parser_test_case_success("2+2",expr(operand(2),operator(+),operand(2))).

test(parser,[ forall(parser_test_case_success(Input,Expected_ast)) ] ) :-
    parser(Input,Ast),
    assertion( Ast == Expected_ast).

parser_test_case_fail("2+3").

test(parser,[ forall(parser_test_case_fail(Input)), fail ] ) :-
    parser(Input,_).

test(generator,all(Generated == ["1+1","1+2","2+1","2+2"]) ) :-
    generator(Generated).

:- end_tests(expr).

语法是明确的，并且只有 4 个有效字符串，而且都是唯一的。

识别器是确定性的，仅返回 true 或 false。
解析器是确定性的并返回唯一的 AST。
生成器是半确定性的，并返回所有 4 个有效的唯一字符串。

测试用例的运行示例。

?- run_tests.
% PL-Unit: expr ........... done
% All 11 tests passed
true.

<小时/>

对丹尼尔的评论进行一些扩展

正如丹尼尔所说

1 + 2 + 3 

可以解析为

(1 + 2) + 3 

或

1 + (2 + 3)

所以 1+2+3 是一个例子，正如您所说的由递归 DCG 指定，正如我指出的，解决问题的常见方法是使用括号开始一个新的上下文。开始一个新的上下文意味着它就像获得一个新的 clean slate重新开始。如果您要创建 AST，只需将新的上下文、项目放在括号之间，作为当前节点的新子树。

关于write_canonical/1 ，这也很有帮助，但要注意运算符的左右结合性。请参阅Associative property

例如

+ 左关联

?- write_canonical(1+2+3).
+(+(1,2),3)
true.

^ 是右结合的

?- write_canonical(2^3^4).
^(2,^(3,4))
true.

即

2^3^4 = 2^(3^4) = 2^81 = 2417851639229258349412352

2^3^4 != (2^3)^4 = 8^4 = 4096

此添加信息的目的是警告您，语法设计充满了隐藏的陷阱，如果您没有上过严格的类(class)并完成了其中的一些操作，您可以轻松创建一个看起来很棒并且效果很好的语法，并且然后几年后发现有一个严重的问题。 AFAIK 虽然 Python 并不含糊，但它确实存在语法问题，它的问题已经足够多了，以至于当 Python 3 创建时，许多问题都得到了修复。因此 Python 3 不向后兼容 Python 2 ( differences )。是的，他们已经进行了更改和库，以便更轻松地在 Python 3 中使用 Python 2 代码，但重点是语法在设计时可以使用更多的分析。