上篇笔记介绍了语法分析相关的一些基础概念,本篇笔记根据龙书第2.5节的内容实现一个针对简单表达式的后缀式语法翻译器Demo。
备注:原书中的demo是java实例,我给出的将是逻辑一致的Python版本的实现。
在简单后缀翻译器代码实现之前,还需要介绍几个基本概念。
1. 自顶向下分析法(top-down parsing)
顾名思义,top-down分析法的思路是推导产生式时,以产生式开始符号作为root节点,从上至下依次构建其子节点,最终构造出语法分析树。在具体实现时,它会把输入字符串从左到右依次扫描一遍,在扫描过程中构建分析树。
假设现有下面的一组文法产生式:
再假设现在要推导的输入字符串为:
for ( ; expr; expr; ) other
则top-down分析法的推导过程如下图所示:
采用的算法步骤为:
1) 以产生式开始符号(即非终结符号"stmt")作为root节点
2) 在标号为非终结符A的节点N上,选择A的一个产生式(在上述示例中,输入的是for语句,故选择for语句对应的产生式),并为该产生式体中的各个符号构造出N的子节点
3) 寻找下一个节点来构造子树,通常选的是语法分析树最左边的尚未扩展的非终结符
4) 重复第2-3步,直至输入串扫描完毕
在算法实现时,有一个重要的约定术语叫做lookahead symbol,它是指输入串中当前正在被扫描的终结符,我们经常会在语法扫描的实现代码中看到lookahead变量,所以有必要知道其来历。
根据上述算法流程对前面推导for语句的示意图做简单说明:
1) 选择产生式开始符号stmt作为root节点
2) 由于输入的是for语句,故选择产生式"for(optexpr; optexpr; optexpr) stmt"进行推导,此时lookahead符号指向终结符号"for",如上图最上面部分的(a)所示。用for产生式中的符号构造root节点的子节点,构造后的分析树如上图中部的(b)所示。
3) root节点的子节点已经构造完,根据算法流程,现在开始构造子节点的子树,虽然"for"节点是当前分析树最左端的尚未扩展的节点句子语法和逻辑分析法,但它是终结符无法扩展子树,此时,若当前被考虑的终结符号与lookahead符号匹配(在本例中都指向"for",正好是匹配的),那么图中语法分析树的箭头和输入串的箭头都要向前推进一步,即语法分析树的节点指向"("节点,lookahead符号指向输入串中的"("。由于"("又是个终结符且与lookahead符号匹配,故再次向前推进一步,此时,语法分析树箭头指向标号为optexpr的非终结符节点,而lookahead符号指向了输入串的终结符";",由于lookahead符号指向的";"与以optexpr开始的产生式无法匹配,故使用空产生式扩展optexpr节点的子节点。
以此类推,最终生成的语法分析树如下图所示:
2. 递归下降分析法(Recursion-Descent Parsing)
递归下降分析法是一种自顶向下的语法分析法,它使用一组递归过程来处理输入串。文法产生式中的每个非终结符均有一个与之关联的过程或函数。
预测分析法(Predictive Parsing)是一种简单的递归下降分析法,在预测分析法中,每个非终结符号对应的过程或函数中的控制流可以由lookahead符号无二义性地确定,即采用预测分析法时,扫描输入串的过程不需要回溯(backtracking)。分析输入串时出现的过程调用序列隐式地定义了该输入串的一颗语法分析树。
本文后面给出的简单表达式的后缀语法翻译器就是采用预测分析法实现的。
3. 左/右递归(Left/Right Recursion)
当一个文法产生式左侧的非终结符与右侧的产生式体开始处的非终结符相同时,就可能发生左递归。具有下面形式的产生式是典型的左递归产生式:
因为该产生式中,非终结符A又出现在产生式体的最左端,在采用递归下降分析法推导这个产生式时,可能会导致无限循环调用,如下图所示。
同理,下面的产生式存在右递归问题:
在采用递归下降分析法推导上面的产生式时,可能会产生右递归无限循环:
所以在使用递归下降分析法前,通常需要对原文法产生式做修改,以便消除左/右递归问题。wikipedia的Left recursion条目总结了一些典型的消除左递归的方法,感兴趣的话,可以去探究。
上面介绍的是略显枯燥的基础概念,下面开始本篇笔记的正题—用Python实现一个简单数学表达式的后缀语法翻译器。
我们的目标是把简单数学表达式的中缀形式翻译成后缀形式,假设给定的语法制导定义如下(其中,左边为文法产生式,右边为附加的语义规则,这些规则定义了从infix到postfix转换的语义规则):
上述语法制导定义对应的语法制导翻译计划如下:
由于上面翻译计划的产生式存在左递归问题(由非终结符expr引起),所以需要做调整以便消除左递归,调整后的语法制导翻译计划如下:
针对上述翻译计划,采用预测分析法,根据龙书第2.5节描述的算法流程,实现了Python版本的简单数学表达式从中缀到后缀语法的翻译器,完整的代码如下。
#!/bin/env python
'''
This demo is inspired by Section 2.5 of the 'Dragon Book':
It implements a syntax-directed translator for simple expressions like '1+2-3'
It translate infix expression into postfix form
'''
class Parser(object):
lookahead = ''
def __init__(self):
print 'Please input an expression with infix form (One Character Per Line):'
Parser.lookahead = raw_input()
self.infix_list = [Parser.lookahead]
self.postfix_list = []
def expr(self):
self.term()
while True:
if Parser.lookahead == '+':
self.match('+')
self.term()
self.postfix_list.append('+')
elif Parser.lookahead == '-':
self.match('-')
self.term()
self.postfix_list.append('-')
else:
print 'raw input is (infix form):'
print ''.join(self.infix_list)
print 'postfix form of the input is:'
print ''.join(self.postfix_list)
return
def term(self):
if self._isdigits(Parser.lookahead):
self.postfix_list.append(Parser.lookahead)
self.match(Parser.lookahead)
else:
print 'term: syntax error'
def match(self, t):
if Parser.lookahead == t:
Parser.lookahead = raw_input()
self.infix_list.append(Parser.lookahead)
else:
print 'match: syntax error'
def _isdigits(self, s):
try:
int(s)
return True
except Exception, e:
return False
class Postfix(object):
def main(self):
parser = Parser()
parser.expr()
print '\n'
if '__main__' == __name__:
postfix = Postfix()
postfix.main()
运行上述脚本,输入合法的简单数学运算( 由产生式可知,目前只支持0-9内的数学加减法)中缀表达式,脚本会将其翻译为后缀语法。交互示例如下:
>>>
Please input an expression with infix form (One Character Per Line):
1
+
2
-
3
-
6
+
5
raw input is (infix form):
1+2-3-6+5
postfix form of the input is:
12+3-6-5+
>>>
备注:脚本目的在于示例如何用预测分析法对输入串做语法翻译,所以实现比较简单粗暴(如输入中缀表达式时每行只能输入一个字符句子语法和逻辑分析法,否则会报错 -_-)。
【参考资料】
1. 龙书第2.3-2.5节
2. wikipedia: Recursive descent parser
3. wikipedia: Left Recursion
========================= EOF ========================
佚名资料
【龙书笔记】用Python实现一个简单数学表达式从中缀到后缀语法的翻译器(采用递的意思
【龙书笔记】用Python实现一个简单数学表达式从中缀到后缀语法的翻译器(采用递相关诗句
- 古诗《涉江采芙蓉》 - - 佚名 - - 《涉江采芙蓉》作者为先秦诗人佚名,古诗《涉江采芙蓉》全文如下:涉江采芙蓉,兰泽多芳草。采之欲遗谁,所思在远道。还顾望旧乡,长路漫浩浩。同心而离居,忧伤以终老。
- 古诗《明月何皎皎》 - - 佚名 - - 明月何皎皎,照我罗床帏。
忧愁不能寐,揽衣起徘徊。
客行虽云乐,不如早旋归。
出户独彷徨,愁思当告谁。
引领还入房,泪下沾裳衣。 - 古诗《九辩》 - - 佚名 - - 《九辩》作者为先秦诗人佚名,古诗《九辩》全文如下:悲哉,秋之为气也!萧瑟兮草木摇落而变衰。憭栗兮若在远行,登山临水兮送将归。泬漻兮天高而气清,寂寥兮收潦而水清。憯
- 古诗《闯王·朝求升,暮求合》 - - 佚名 - - 《闯王·朝求升,暮求合》作者为先秦诗人佚名,古诗《闯王·朝求升,暮求合》全文如下:朝求升,暮求合,近来贫汉难存活。早早开门拜闯王,管教大小都欢悦。杀牛羊,备酒浆,开了城
- 古诗《去者日以疏》 - - 佚名 - - 《去者日以疏》作者为先秦诗人佚名,古诗《去者日以疏》全文如下:去者日以疏,生者日已亲。出郭门直视,但见丘与坟。古墓犁为田,松柏摧为薪。白杨多悲风,萧萧愁杀人。思还
- 古诗《冉冉孤生竹》 - - 佚名 - - 《冉冉孤生竹》作者为先秦诗人佚名,古诗《冉冉孤生竹》全文如下:冉冉孤生竹,结根泰山阿。与君为新婚,菟丝附女萝。菟丝生有时,夫妇会有宜。千里远结婚,悠悠隔山陂。思君
- 古诗《孟冬寒气至》 - - 佚名 - - 《孟冬寒气至》作者为先秦诗人佚名,古诗《孟冬寒气至》全文如下:孟冬寒气至,北风何惨栗。愁多知夜长,仰观众星列。三五明月满,四五蟾兔缺。客从远方来,遗我一书札。上言
- 古诗《今日良宴会》 - - 佚名 - - 《今日良宴会》作者为先秦诗人佚名,古诗《今日良宴会》全文如下:今日良宴会,欢乐难具陈。弹筝奋逸响,新声妙入神。令德唱高言,识曲听其真。齐心同所愿,含意俱未申。人生
- 古诗《孺子歌》 - - 佚名 - - 《孺子歌》作者为先秦诗人佚名,古诗《孺子歌》全文如下:沧浪之水清兮,可以濯我缨。沧浪之水浊兮,可以濯我足。
- 古诗《客从远方来》 - - 佚名 - - 《客从远方来》作者为先秦诗人佚名,古诗《客从远方来》全文如下:客从远方来,遗我一端绮。相去万余里,故人心尚尔。文彩双鸳鸯,裁为合欢被。著以长相思,缘以结不解。以胶
- 古诗《庭中有奇树》 - - 佚名 - - 《庭中有奇树》作者为先秦诗人佚名,古诗《庭中有奇树》全文如下:庭中有奇树,绿叶发华滋。攀条折其荣,将以遗所思。馨香盈怀袖,路远莫致之。此物何足贵,但感别经时。
- 古诗《驱车上东门》 - - 佚名 - - 《驱车上东门》作者为先秦诗人佚名,古诗《驱车上东门》全文如下:驱车上东门,遥望郭北墓。白杨何萧萧,松柏夹广路。下有陈死人,杳杳即长暮。潜寐黄泉下,千载永不寤。浩浩
- 古诗《明月皎夜光》 - - 佚名 - - 《明月皎夜光》作者为先秦诗人佚名,古诗《明月皎夜光》全文如下:明月皎夜光,促织鸣东壁。玉衡指孟冬,众星何历历。白露沾野草,时节忽复易。秋蝉鸣树间,玄鸟逝安适。昔我
- 古诗《青青陵上柏》 - - 佚名 - - 《青青陵上柏》作者为先秦诗人佚名,古诗《青青陵上柏》全文如下:青青陵上柏,磊磊涧中石。人生天地间,忽如远行客。斗酒相娱乐,聊厚不为薄。驱车策驽马,游戏宛与洛。洛中
- 古诗《赓歌·股肱喜哉》 - - 佚名 - - 《赓歌·股肱喜哉》作者为先秦诗人佚名,古诗《赓歌·股肱喜哉》全文如下:股肱喜哉。元首起哉。百工熙哉。元首明哉。股肱良哉。庶事康哉。元首丛脞哉。股肱惰哉。万
- 古诗《采薇歌》 - - 佚名 - - 《采薇歌》作者为先秦诗人佚名,古诗《采薇歌》全文如下:登彼西山兮,采其薇矣。以暴易暴兮,不知其非矣。神农虞夏忽焉没兮,我适安归矣。于嗟徂兮,命之衰矣。
- 古诗《生年不满百》 - - 佚名 - - 《生年不满百》作者为先秦诗人佚名,古诗《生年不满百》全文如下:生年不满百,常怀千岁忧。昼短苦夜长,何不秉烛游。为乐当及时,何能待来兹。愚者爱惜费,但为後世嗤。仙人
- 古诗《迢迢牵牛星》 - - 佚名 - - 《迢迢牵牛星》作者为先秦诗人佚名,古诗《迢迢牵牛星》全文如下:迢迢牵牛星,皎皎河汉女。纤纤擢素手,札札弄机杼。终日不成章,泣涕零如雨。河汉清且浅,相去复几许。盈盈
- 古诗《凛凛岁云暮》 - - 佚名 - - 《凛凛岁云暮》作者为先秦诗人佚名,古诗《凛凛岁云暮》全文如下:凛凛岁云暮,蝼蛄夕鸣悲。凉风率已厉,游子寒无衣。锦衾遗洛浦,同袍与我违。独宿累长夜,梦想见容辉。良人
- 古诗《东城高且长》 - - 佚名 - - 《东城高且长》作者为先秦诗人佚名,古诗《东城高且长》全文如下:东城高且长,逶迤自相属。回风动地起,秋草萋已绿。四时更变化,岁暮一何速。晨风怀苦心,蟋蟀伤局促。荡涤
佚名的名句
- 中式婚礼祝福语 - - - 佚名 - - - 《网络整理》
- 绿色环保的语句 - - - 佚名 - - - 《网络整理》
- 描写“冬天”的好词好句好段好诗,用在作文绝对加分!收藏 - - - 佚名 - - - 《网络整理》
- 回家开心的句子 回家心情愉快的句子(精选55句) - - - 佚名 - - - 《网络整理》
- 关于清明的24句话! - - - 佚名 - - - 《网络整理》
- 水浒传中有个禁军教头,他先败张清再战卢俊义,武功或在林 - - - 佚名 - - - 《网络整理》
- 璀璨的夜光杯 - - - 佚名 - - - 《网络整理》
- 部编版一年级下册语文仿写句子汇总+各类句子专项题型 - - - 佚名 - - - 《网络整理》
- 描写环保的优美句子 - - - 佚名 - - - 《网络整理》
- 不要被陶渊明骗了,古代田园生活没那么美好 - - - 佚名 - - - 《网络整理》
- “琵琶起舞换新声, 总是关山旧别情。”王昌龄《从军行 - - - 佚名 - - - 《网络整理》
- 春梅的诗句 - - - 佚名 - - - 《网络整理》
- 满月酒主持人开场白 - - - 佚名 - - - 《网络整理》
- 从军行王昌龄其二朗诵 - - - 佚名 - - - 《网络整理》
- 满月酒宴会讲话稿通用主持词开场白 - - - 佚名 - - - 《网络整理》
- 关于珍惜时间的名言和谚语 - - - 佚名 - - - 《网络整理》
- 习近平:坚定理想信念 补足精神之钙 - - - 佚名 - - - 《网络整理》
- 珍惜时间的名言警句励志语 - - - 佚名 - - - 《网络整理》
- 叠字诗词 , 意境唯美又经典! - - - 佚名 - - - 《网络整理》
- 形容珍惜时间的谚语 - - - 佚名 - - - 《网络整理》