木兰编程语言重现:优先级,一个过不去的坎

注:项目目标见码云代码库

上周就复现了一个语法,支持了这样的乘法6/2(1+2),结果为 1。

实现中,用到了针对语法规则的优先级设置。虽然 rply 有文档说明,但死磕过后仍然不明所以然。将调试过程记录在此,最后有问题请教各位。

演示

先举个例子(熟悉者请跳过直接看“正题”部分)。很早就复现了四则运算,比如:

10 + 3 * 6 / 5 => 13 

相关的优先级(precedence)设置是开头针对词(token)的部分,从低到高排列:

    分析器母机 = ParserGenerator(
        规则,
        precedence=[
          ...
            ('left', [不等于, 等于]),
          ...
            ('left', [加, 减]),
            ('left', [星号, 除]),
          ...

            ('right', [乘方])

注:上面的“除”代表的是原本支持的/除法符号。

比方说,现在想扩展一个语法,支持÷这个除法符号,除了添加一个词“除法”——分词器母机.add(除法, '÷')、增加一个语法规则——@分析器母机.production(语法.二元表达式.成分(语法.表达式, 除法, 语法.表达式))之外,还需要照样把除法添加到优先级设置:

('left', [星号, 除, 除法]),

于是就可以支持:

10 + 3 * 6 ÷ 5 => 13 

假如不慎将除法的优先级设置高了,比如和乘方一样:

('right', [乘方, 除法])

那么像10 + 3 * 4 ÷ 5原本应该是 12,但现在会是 10,因为 4÷5 先执行后结果为 0。

假如干脆不设置除法的优先级,那么10 + 3 * 6 ÷ 5就会输出这样的玩意:

.../木兰/prototype/分析器/语法分析器.py:884: ParserGeneratorWarning: 19 shift/reduce conflicts
  分析器 = LRParser(分析器母机.build())
5 

可以看到最后输出了 5,应该是解析为了(10 + 3 * 6) ÷ 5。

但报警告有shift/reduce冲突,要是能提示冲突细节多好。

那么如果在这个语法规则添加设置,使之优先级与“除”相同,是否能达到正确效果呢?

@分析器母机.production(语法.二元表达式.成分(语法.表达式, 除法, 语法.表达式), precedence=除)

上面的shift/reduce冲突倒是没了,但结果仍为 5。而且,即使这里优先级设最低、最高,都是同样效果。

恢复到precedence=除后作更多测试:

10 + 3 ÷ 2 * 6 => 36,((10+3)/2)*6
10 + 3 ^ 2 ÷ 2 => 9, (10+(3^2))/2
10 + 3 ÷ 2 ^ 2 => 3, (10+3)/(2^2)
10 + 3 ÷ 2 / 2 => 3, ((10+3)/2)/2
10 + 3 ÷ 2 + 2 => 8, ((10+3)/2)+2 

如果改为比“除”优先级低的precedence=加,两个结果变了:

10 + 3 ÷ 2 * 6 => 1,(10+3)/(2*6)
10 + 3 ^ 2 ÷ 2 => 9
10 + 3 ÷ 2 ^ 2 => 3
10 + 3 ÷ 2 / 2 => 13, (10+3)/(2/2)
10 + 3 ÷ 2 + 2 => 8 

如果改为比“加”更低的precedence=等于,一个结果又变了:

10 + 3 ÷ 2 + 2 => 3, (10+3)/(2+2) 

尚未看 rply 实现,个人的推测是,由于这个优先级是针对的这条语法规则,而非“÷”这个词,因此,在“÷”左边所有部分会被解析为一个“表达式”,而右边高于设定优先级的运算部分会合在一个“表达式”。

正题

前不久支持的范围表达式,格式为:-1..4 by 2,范围表达式的三个规则如下:

    @分析器母机.production(语法.范围表达式.成分(语法.表达式, 点点, 语法.表达式))
    @分析器母机.production(语法.范围表达式.成分(语法.表达式, 点点小于, 语法.表达式))
    @分析器母机.production(语法.范围表达式.成分(语法.范围表达式, 连词_每隔, 语法.表达式))

需要在下面的表达式语法规则中设置优先级为“等于”,比“连词_每隔”(by)低一级。

    @分析器母机.production(语法.表达式.成分(语法.范围表达式), precedence=等于)

否则会报错:

分析器.错误.语法错误: 文件 "测试/数据结构/范围.ul", 第4行, 第13列, 没认出这个词 "by"
print(-1..4 by 2)
            ^ 

看来只有比 by 低,才会将整个识别为“范围表达式”(下面规则),而不是将前半段识别为“表达式”

    @分析器母机.production(语法.范围表达式.成分(语法.范围表达式, 连词_每隔, 语法.表达式))

那么为何不设置为优先级更低呢?

最近的这个省乘号乘法,除了下面三个语法规则:

    @分析器母机.production(语法.表达式.成分(语法.多项式乘法))

    @分析器母机.production(语法.多项式乘法.成分(语法.数, 语法.表达式前缀))
    @分析器母机.production(语法.多项式乘法.成分(语法.数, 语法.首要表达式))

还需要在这条看似不搭嘎的规则添加优先级设置:

@分析器母机.production(语法.表达式.成分(语法.数), precedence=等于)

否则也会报警告ParserGeneratorWarning: 1 shift/reduce conflict。

应该,也是为了不把2a中的2解析为“表达式”,而是将整体解析为“多项式乘法”。

这个优先级设置与上面的范围表达式的设置相同,有何用意吗?

请不吝赐教!

展开阅读全文

页面更新:2024-05-02

标签:优先级   木兰   母机   乘方   多项式   连词   星号   除法   分析器   乘法   表达式   正题   语法   成分   冲突   规则   科技

1 2 3 4 5

上滑加载更多 ↓
推荐阅读:
友情链接:
更多:

本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828  

© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号

Top