BNF 语法和运算符结合性

发布于 09-30 16:31 字数 874 浏览 6 评论 0原文

(首先这不是硬件,我有所有答案)

我有一个简单的BNF语法

<UNIT> ::= ( <CLAUSE> ) | a | b | c
<ITEM> ::= not <UNIT> | <UNIT>
<CLAUSE> ::= <CLAUSE> and <PHRASE> | <PHRASE>
<PHRASE> ::= <ITEM> | <ITEM> or <PHRASE>

and 运算符是左关联(左手递归) or 运算符是右关联的(这次是右递归)

给定表达式 c and b or not a and (not b or c ),为什么是最正确的“and”在解析树中更高?
顺便说一句,我看到 c **and** b 或不是 a 和(不是 b 或 c ) 最左边应该在解析树中更高。

我们的教授提供了这个答案:

这是用 lispy 表示法表示的解析树。

(clause (clause (clause (phrase (item (unit 'c'))))
'and'
(phrase (item (unit 'b'))
'or'
(phrase (item 'not'
(unit 'a')))))
**'and'** // is higher in parse tree
(phrase (item (unit '('
(clause (phrase (item 'not’(unit 'b'))
'or'
(phrase (item (unit 'c')))))
')' ))))

(First of all this is not HW, I have all the answers)

I have a simple BNF grammar

<UNIT> ::= ( <CLAUSE> ) | a | b | c
<ITEM> ::= not <UNIT> | <UNIT>
<CLAUSE> ::= <CLAUSE> and <PHRASE> | <PHRASE>
<PHRASE> ::= <ITEM> | <ITEM> or <PHRASE>

and operator is Left associative (left-hand recursive )
or operator is Right associative (this time, it is right-hand recursive )

Given expression c and b or not a and ( not b or c ), why is most right "and" is higher in the parse tree ?
The way, I see c **and** b or not a and ( not b or c ) left most should be higher in the parse tree.

Our professor provided this answer:

Here is the parse tree in a lispy notation.

(clause (clause (clause (phrase (item (unit 'c'))))
'and'
(phrase (item (unit 'b'))
'or'
(phrase (item 'not'
(unit 'a')))))
**'and'** // is higher in parse tree
(phrase (item (unit '('
(clause (phrase (item 'not’(unit 'b'))
'or'
(phrase (item (unit 'c')))))
')' ))))

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

南风几经秋2024-10-07 16:31:47

给出的 BNF 语法似乎与解析树一致,并且与“and”应该是左关联的主张一致。如果你想用这个语法产生“a and b and c”,从“Clause”开始,你可以这样开始:

  1. Clause
  2. Clause and Phrase

此时,Phrase 不能变成“b and c” (不带括号)因为只有从句才能产生“and”。短语必须发展成“c”,第二行的从句可以发展成“a and b”。这将迫使最右边的“和”在解析树中位于更高的位置。

由于解析树中的较高元素是最后评估的,因此这与运算符“and”是左关联的声明是一致的。

The BNF grammar given seems consistent with the parse tree, and consistent with the claim that "and" is supposed to be left-associative. If you want to produce "a and b and c" using this grammar, starting with "Clause", you start this way:

  1. Clause
  2. Clause and Phrase

At which point, Phrase cannot become "b and c" (without parentheses) because only clauses can produce "and". Phrase has to develop into "c", and the Clause on the second line can become "a and b". This will force the rightmost "and" to be higher in the parse tree.

Since higher elements in the parse tree are last to evaluate, this is consistent with the claim that the operator "and" is left associative.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文