解析器 DCG 不是确定性的是否合适？
Is it appropriate for a parser DCG to not be deterministic?
我正在为查询引擎编写解析器。我的解析器 DCG query 不是确定性的。
我将以关系方式使用解析器来检查和综合查询。
解析器 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.
什么时候用它来检查公式？
要问自己的第一个问题是你的语法确定性，或者在语法术语中，unambiguous. This is not asking if your DCG is deterministic, but if the grammar is unambiguous. That can be answered with basic parsing concepts, no use of DCG is needed to answer that question. In other words, is there only one way to parse a valid input. The standard book for this is "Compilers : principles, techniques, & tools" (WorldCat)
现在您实际上是在询问解析的三种不同用途。
- 一个识别器。
- 解析器。
- 一台发电机。
如果你的语法没有歧义，那么
- 对于识别器，答案应该只对可以解析的有效输入为真，对无效输入为假。
- 对于解析器来说，它应该是确定性的，因为只有一种方法可以解析输入。解析器和识别器之间的区别在于，识别器只有 return 真或假，而解析器会 return 更多信息，通常是抽象语法树。
- 对于生成器，它应该是半确定性的，以便它可以生成多个结果。
所有这些都可以用一个 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 个唯一的有效字符串。
识别器是确定性的，只有 return 是真或假。
解析器是确定性的并且 return 是一个唯一的 AST。
生成器是半确定性的并且 returns 所有 4 个有效的唯一字符串。
测试用例的示例 运行。
?- run_tests.
% PL-Unit: expr ........... done
% All 11 tests passed
true.
对 Daniel
的评论进行一些扩展
正如丹尼尔所说
1 + 2 + 3
可以解析为
(1 + 2) + 3
或
1 + (2 + 3)
所以 1+2+3 是您所说的示例 is specified by a recursive DCG 并且正如我指出的，解决该问题的常见方法是使用括号来开始新的上下文。开始一个新的上下文的意思是，它就像得到一个新的clean slate重新开始。如果你正在创建一个 AST，你只需将新的上下文、项目放在括号之间，作为当前节点的新子树。
关于write_canonical/1, this is also helpful but be aware of left and right associativity of operators. See 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 并完成其中的一些，您可以轻松创建一个语法看起来很棒，效果很好，但几年后发现有严重问题。虽然 Python 不是模棱两可的 AFAIK，但它确实存在语法问题，它有足够多的问题以至于在创建 Python 3 时，许多问题都得到了修复。所以 Python 3 不向后兼容 Python 2 (differences)。是的，他们进行了更改和库，以便更容易地使用 Python 2 代码和 Python 3，但关键是语法在设计时可以使用更多分析。
唯一 代码应该是非确定性的原因是您的问题有多个答案。在那种情况下，您当然希望您的查询有多个解决方案。但是，即便如此，如果可能的话，您还是希望不要在最后一个解决方案之后留下一个选择点。
我的意思是：
"What is the smaller of two numbers?"
min_a(A, B, B) :- B < A.
min_a(A, B, A) :- A =< B.
所以现在你问，"what is the smaller of 1 and 2" 你期望的答案是“1”：
?- min_a(1, 2, Min).
Min = 1.
?- min_a(2, 1, Min).
Min = 1 ; % crap...
false.
?- min_a(2, 1, 2).
false.
?- min_a(2, 1, 1).
true ; % crap...
false.
所以这不是糟糕的代码，但我认为它仍然是废话。这就是为什么对于两个数字中较小的一个，您会使用类似 the min() function in SWI-Prolog.
的原因
同样，说你想问，"What are the even numbers between 1 and 10"；您编写查询：
?- between(1, 10, X), X rem 2 =:= 0.
X = 2 ;
X = 4 ;
X = 6 ;
X = 8 ;
X = 10.
...这很好，但是如果您要求输入 3 的倍数，您会得到：
?- between(1, 10, X), X rem 3 =:= 0.
X = 3 ;
X = 6 ;
X = 9 ;
false. % crap...
"low-hanging fruit" 是您作为程序员会看到不可能存在非确定性的情况，但由于某种原因，您的 Prolog 无法从您编写的代码中推断出这一点。在大多数情况下，您可以采取一些措施。
关于你的实际问题。如果可以，请编写代码，使非确定性仅当您要问的问题有多个答案时。当您使用 DCG 进行解析和生成时，这有时意味着您最终会得到两个代码路径。它感觉笨拙，但更容易编写、阅读、理解，并且可能提高效率。请注意，请查看 。我不能确定，但 OP 运行 遇到的问题几乎可以肯定是由不必要的非确定性引起的。较大的输入可能会发生很多的选择点，有很多内存无法回收，大量的处理时间进入簿记，巨大的解决方案遍历树只是为了得到（如预期的）没有解决方案....你明白了。
关于我的意思的例子，你可以看看the implementation of library(dcg/basics) in SWI-Prolog。注意几点：
- 文档非常明确地说明了什么是确定性的，什么不是，以及非确定性应该如何对客户端代码有用；
- 在必要时使用剪切来去除无用的选择点；
number//1的实现（朝下）可以"generate extract a number".
（提示：在编写自己的解析器时使用此库中的原语！）
希望这个冗长的回答对您有用。
我正在为查询引擎编写解析器。我的解析器 DCG query 不是确定性的。
我将以关系方式使用解析器来检查和综合查询。
解析器 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.
什么时候用它来检查公式？
要问自己的第一个问题是你的语法确定性，或者在语法术语中，unambiguous. This is not asking if your DCG is deterministic, but if the grammar is unambiguous. That can be answered with basic parsing concepts, no use of DCG is needed to answer that question. In other words, is there only one way to parse a valid input. The standard book for this is "Compilers : principles, techniques, & tools" (WorldCat)
现在您实际上是在询问解析的三种不同用途。
- 一个识别器。
- 解析器。
- 一台发电机。
如果你的语法没有歧义，那么
- 对于识别器，答案应该只对可以解析的有效输入为真，对无效输入为假。
- 对于解析器来说，它应该是确定性的，因为只有一种方法可以解析输入。解析器和识别器之间的区别在于，识别器只有 return 真或假，而解析器会 return 更多信息，通常是抽象语法树。
- 对于生成器，它应该是半确定性的，以便它可以生成多个结果。
所有这些都可以用一个 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 个唯一的有效字符串。
识别器是确定性的，只有 return 是真或假。
解析器是确定性的并且 return 是一个唯一的 AST。
生成器是半确定性的并且 returns 所有 4 个有效的唯一字符串。
测试用例的示例 运行。
?- run_tests.
% PL-Unit: expr ........... done
% All 11 tests passed
true.
对 Daniel
的评论进行一些扩展正如丹尼尔所说
1 + 2 + 3
可以解析为
(1 + 2) + 3
或
1 + (2 + 3)
所以 1+2+3 是您所说的示例 is specified by a recursive DCG 并且正如我指出的，解决该问题的常见方法是使用括号来开始新的上下文。开始一个新的上下文的意思是，它就像得到一个新的clean slate重新开始。如果你正在创建一个 AST，你只需将新的上下文、项目放在括号之间，作为当前节点的新子树。
关于write_canonical/1, this is also helpful but be aware of left and right associativity of operators. See 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 并完成其中的一些，您可以轻松创建一个语法看起来很棒，效果很好，但几年后发现有严重问题。虽然 Python 不是模棱两可的 AFAIK，但它确实存在语法问题，它有足够多的问题以至于在创建 Python 3 时，许多问题都得到了修复。所以 Python 3 不向后兼容 Python 2 (differences)。是的，他们进行了更改和库，以便更容易地使用 Python 2 代码和 Python 3，但关键是语法在设计时可以使用更多分析。
唯一 代码应该是非确定性的原因是您的问题有多个答案。在那种情况下，您当然希望您的查询有多个解决方案。但是，即便如此，如果可能的话，您还是希望不要在最后一个解决方案之后留下一个选择点。
我的意思是：
"What is the smaller of two numbers?"
min_a(A, B, B) :- B < A.
min_a(A, B, A) :- A =< B.
所以现在你问，"what is the smaller of 1 and 2" 你期望的答案是“1”：
?- min_a(1, 2, Min).
Min = 1.
?- min_a(2, 1, Min).
Min = 1 ; % crap...
false.
?- min_a(2, 1, 2).
false.
?- min_a(2, 1, 1).
true ; % crap...
false.
所以这不是糟糕的代码，但我认为它仍然是废话。这就是为什么对于两个数字中较小的一个，您会使用类似 the min() function in SWI-Prolog.
同样，说你想问，"What are the even numbers between 1 and 10"；您编写查询：
?- between(1, 10, X), X rem 2 =:= 0.
X = 2 ;
X = 4 ;
X = 6 ;
X = 8 ;
X = 10.
...这很好，但是如果您要求输入 3 的倍数，您会得到：
?- between(1, 10, X), X rem 3 =:= 0.
X = 3 ;
X = 6 ;
X = 9 ;
false. % crap...
"low-hanging fruit" 是您作为程序员会看到不可能存在非确定性的情况，但由于某种原因，您的 Prolog 无法从您编写的代码中推断出这一点。在大多数情况下，您可以采取一些措施。
关于你的实际问题。如果可以，请编写代码，使非确定性仅当您要问的问题有多个答案时。当您使用 DCG 进行解析和生成时，这有时意味着您最终会得到两个代码路径。它感觉笨拙，但更容易编写、阅读、理解，并且可能提高效率。请注意，请查看
关于我的意思的例子，你可以看看the implementation of library(dcg/basics) in SWI-Prolog。注意几点：
- 文档非常明确地说明了什么是确定性的，什么不是，以及非确定性应该如何对客户端代码有用；
- 在必要时使用剪切来去除无用的选择点；
number//1的实现（朝下）可以"generate extract a number".
（提示：在编写自己的解析器时使用此库中的原语！）
希望这个冗长的回答对您有用。