消除抽象语法中的歧义以编写 DCG 解析器 Prolog [英] Remove Ambiguity in abstract syntax in other to write DCG parser Prolog

问题描述

P => 程序K => 阻止

P => Program K => Block

S => 单命令

C => 命令

E => 表达式

B => 布尔表达式

I => 标识符

N > 数字

P ::= K.

K ::= 开始 C 结束

K ::= begin C end

C ::= C1 ;C2 |

C ::= C1 ; C2 | S

S ::= I := E |如果 (B) 那么 S |if (B) then S1 else S2 |而 (B) 做 S |重复 C 直到 (B) |克|打印E

S ::= I := E | if (B) then S | if (B) then S1 else S2 | while (B) do S | repeat C until (B) | K | print E

E ::= − E |E1 + E2 |E1 - E2 |E1 E2 |E1 div E2 |E1 模式 E2 |(E) |我|否

E ::= − E | E1 + E2 | E1 − E2 | E1 E2 | E1 div E2 | E1 mod E2 | (E) | I | N

B ::= E1 = E2 |E1 > E2 |E1＜E2 |E1 != E2 |不是 B |B1和B2 |B1 或 B2 |(乙)

B ::= E1 = E2 | E1 > E2 | E1 < E2 | E1 != E2 | not B | B1 and B2 | B1 or B2 | (B)

我应该消除 E 和 B 中的歧义，以便我可以在 prolog 中编写 DCG 解析器.

I am supposed to remove ambiguities in E and B so that I can write a DCG parser in prolog.

推荐答案

Prolog 自上而下求值，然后 LL 语法技术 可以适应.DCG比LL(1)更强大，但仍然必须消除左递归.

Prolog evaluates top down, then LL grammar techniques can be adapted. DCG are more powerful than LL(1), but left recursion must still be eliminated.

B 更容易处理:left factor 产生式.

B is easier to handle: left factor the production.

B ::= E Bx | not B | (B)
Bx ::= = E | > E | < E | != E | and B | or B

E 更难，因为缺少 mul 标记会引入更多的歧义.暂定

E is harder, because the miss mul token introduces still more ambiguity. Tentatively

E ::= − E | (E) | I | N | El
El ::= Ex E | epsilon
Ex ::= + El | − El | div El | mod El

DCG 中的 epsilon(空产生)可以这样写

epsilon (empty production) in DCG can be written this way

epsilon --> [].

如果您需要处理优先级和关联性(在 B 和 E 中)，您将需要做更多的工作.您可以参考 this 较旧的答案以了解工作架构.

If you need to handle precedence and associativity (in both B and E) you will need more work. You can refer to this older answer for a working schema.

这篇关于消除抽象语法中的歧义以编写 DCG 解析器 Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！