删除其他抽象语法中的歧义以编写 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 |S

C ::= C1 ; C2 | S

S ::= I := E |如果 (B) 则 S |如果 (B) 则 S1 否则 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 分区 E2 |E1 模组 E2 |(五) |我 |否

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)

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屋！