【Python】代码实现LL(1),LR(1)上下文无关文法（Stack()类）

冷不防 2023-02-13 14:45 76阅读 0赞

任务要求

针对书上第三章中的表达式文法，采用LL(1)、LR(1)进行分析

相关文法（需要进行消除左递归等操作）：
在这里插入图片描述

顺手分享一下课本资源好了（可能不是最新版，排版略有点别扭）
后文的书上内容就是指这本书：[编译原理].陈意云.文字版
提取码：e0ag

LL1介绍

LL(1):从左往右处理输入，最左推导，向前展望1个符号的，不带回溯的自上而下的算法，是上下文无关文法的子集。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

LL1代码实现

书上P59-60
在这里插入图片描述
在这里插入图片描述

  1. #LL1
  2. import pandas as pd
  3. class Stack:
  4.     def __init__(self):
  5.         self.values = "$E"
  7.     def push(self, product):
  8.         while product[-1:]!='→':
  9.             if(product[-1:]=='\'' or product[-1:]=='d'):
  10.                 self.values+=product[-2:]
  11.                 product=product[0:-2]
  12.             else:
  13.                 self.values+=product[-1:]
  14.                 product=product[0:-1]
  16.     def pop(self):
  17.         if(self.values[-1:]=='\''or self.values[-1:]=='d'):
  18.             self.values=self.values[:-2];
  19.         else:
  20.             self.values=self.values[:-1]
  22.     def top(self):
  23.         if(self.values[-1:]=='\''or self.values[-1:]=='d'):
  24.             return self.values[-2:]
  25.         else:
  26.             return self.values[-1:]
  28.     def empty(self):
  29.         return len(self.values) == 0
  31. def Next_Char():#获取下一个词法记号
  32.     global pend_input
  33.     if(pend_input[0:2]=="id"):
  34.          pend_input=pend_input[2:]
  35.          return "id"
  36.     else:
  37.         t=pend_input[0:1]
  38.         pend_input=pend_input[1:]
  39.         return t
  41. dic={
  42.     #手工构造预测分析表
  43. 'id':['E→TE\'','error','T→FT\'','error','F→id'],
  44. '+':['error','E\'→+TE\'','error','T\'→ε','error'],
  45. '*':['error','error','error','T\'→*FT\'','error'],
  46. '(':['E→TE\'','error','T→FT\'','error','F→(E)'],
  47. ')':['error','E\'→ε','error','T\'→ε','error'],
  48. '$':['error','E\'→ε','error','T\'→ε','error']}
  49. Analysis_table=pd.DataFrame(dic,index=['E','E\'','T','T\'','F'])
  51. if __name__ == '__main__':
  52.     stk = Stack()           #构造自定义栈
  53.     #pend_input=input()+'$' #记得在输入内容后加上表示终止的"$"符号
  54.     pend_input='id*id+id$'  #可手动输入亦可提前输入'待处理的输入内容'
  55.     pend_head=Next_Char()   #取出第一个待处理的符号
  56.     print("预测分析器接受输入id*id+id的部分动作（与书上稍有不同）")
  57.     print("%-15s"%"栈","%-15s"%"输入","%+10s"%"输出")
  58.     while(stk.empty()==False):              
  59.         if stk.top()==pend_head: 
  60.             if pend_head!='$':
  61.                 print('----------------成功匹配符号:{}-------------------'.format(pend_head))
  62.             pend_head=Next_Char()
  63.             stk.pop()
  64.         else:
  65.             product=Analysis_table[pend_head][stk.top()]#获取产生式
  66.             if product=='error':
  67.                 print('Error  Skip!')
  68.                 stk.pop()
  69.             else:
  70.                 print("%-15s"%stk.values,"%-15s"%str(pend_head+pend_input),"%+15s"%product)
  71.                 stk.pop()
  72.                 if(product[-1:]!='ε'):#对于产生空串的产生式，只需弹栈，不需入栈
  73.                     stk.push(product)

手动构造的预测分析表：
在这里插入图片描述

预测分析器接受输入id * id + id的相关动作：
在这里插入图片描述

LR1简略介绍

LR(1)：从左往右处理输入，构造一个最右推导的逆过程（规范规约），向前看1个符号的，自下而上的算法，是上下文无关文法的子集。

LR文法：我们能为之构造出所有条目都唯一的LR分析表。

LR分析器特点：适用于一大类上下文无关文法，效率高。

句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。

活前缀：右句型的前缀，该前缀不超过最右句柄的右端。

在这里插入图片描述

LR1代码

书上P73-74

在这里插入图片描述
r后面的数字代表按第几个产生式做归约；s代表移进，它后面的数字转移到哪个状态。产生式：
在这里插入图片描述
在这里插入图片描述

  1. #LR1
  2. import pandas as pd
  3. class Stack:
  4.     def __init__(self):
  5.         self.values = "0"
  6.     def push(self, s):
  7.         self.values=self.values+s
  8.         def __init__(self):
  9.             self.values = "0"             
  10.     def pop(self):
  11.         if(self.values[-2:]=='id'or self.values[-2:]=='10'or self.values[-2:]=='11'):
  12.             self.values=self.values[:-2]
  13.         else:
  14.             self.values=self.values[:-1]
  15.     def top(self):
  16.         if(self.values[-2:]=='10'or self.values[-2:]=='id' or self.values[-2:]=='11'):
  17.             return self.values[-2:]
  18.         else:
  19.             return self.values[-1:]
  20. class Input_Token:
  21.     def __init__(self):
  22.         self.values = ""
  23.     def Get_Token(self):#获取待处理字符串pend_input中下一个词法记号
  24.         if(self.values[0:2]=="id"):
  25.              self.values=self.values[2:]
  26.              return "id"
  27.         else:
  28.             s=self.values[0:1]
  29.             self.values=self.values[1:]
  30.             return s
  31.     def Show_Token(self):#查看待处理字符串pend_input的下一个词法记号（不取出）
  32.         if (self.values[0:2] == "id"):
  33.             return "id"
  34.         else:
  35.             s = self.values[0:1]
  36.             return s
  38. def Len_Right(p):
  39.     p_char=p[p.find('→')+1:]
  40.     if p_char=='id':
  41.         return 1
  42.     else:
  43.         return len(p_char)
  45. def LR1(head,top):#分析程序
  46.     action=SLR[head][top]
  47.     if action=='acc':#接受
  48.         print("%-9s"%stk.values,"%+9s"%pend_input.values,"%+6s"%"接受")
  49.         return False
  50.     else:
  51.         if action[0]=='s':#移进
  52.             print("%-9s"%stk.values,"%+9s"%pend_input.values,"%+6s"%"移进")
  53.             stk.push(pend_input.Get_Token())
  54.             stk.push(action[1:])
  55.         elif action[0]=='r':#归约
  56.             production=Production[int(action[1:])]
  57.             print("%-9s"%stk.values,"%+9s"%pend_input.values,"%+5s"%"按",production,"归约")
  58.             for i in range(Len_Right(production)*2): #按照产生式右边长度的2倍出栈(1字符跟1数字)
  59.                 stk.pop()
  60.             top_num=stk.top()
  61.             left=production[0] #获取产生式左边的字符
  62.             stk.push(left)
  63.             stk.push(SLR[left][top_num])
  64.         else:
  65.             print('Error!\n Exit!')
  66.             return False
  67.         return True
  69. dic={
  70.     'id':['s5',' ',' ',' ','s5',' ','s5','s5',' ',' ',' ',' '],
  71.       '+':[' ','s6','r2','r4',' ','r6',' ',' ','s6','r1','r3','r5'],
  72.       '*':[' ',' ','s7','r4',' ','r6',' ',' ',' ','s7','r3','r5'],
  73.       '(':['s4',' ',' ',' ','s4',' ','s4','s4',' ',' ',' ',' ',],
  74.       ')':[' ',' ','r2','r4',' ','r6',' ',' ','s11','r1','r3','r5'],
  75.       '$':[' ','acc','r2','r4',' ','r6',' ',' ',' ','r1','r3','r5'],
  76.       'E':['1',' ',' ',' ','8',' ',' ',' ',' ',' ',' ',' '],
  77.       'T':['2',' ',' ',' ','2',' ','9',' ',' ',' ',' ',' ',],
  78.       'F':['3',' ',' ',' ','3',' ','3','10',' ',' ',' ',' ']}
  79. SLR=pd.DataFrame(dic,index=['0','1','2','3','4','5','6','7','8','9','10','11'])#分析表
  80. Production=['null','E→E+T','E→T','T→T*F','T→F','F→(E)','F→id']#产生式   
  81. if __name__=='__main__':
  82.     stk = Stack()
  83.     pend_input=Input_Token()
  84.     pend_input.values='id*id+id$'
  85.     print("———————————————LR分析器———————————————")
  86.     print("%-7s"%"栈","%+8s"%"输入","%+6s"%"动作")
  87.     while(True):
  88.         if LR1(pend_input.Show_Token(),stk.top())==False:
  89.             break
  90.     print("——————————————————————————————————————")

分析表（action表）
描述？
实验结果：
在这里插入图片描述

LR分析方法和LL分析方法的比较

部分参考资料" class="reference-link">在这里插入图片描述 部分参考资料

编译原理：语法分析2-非递归的预测分析

编译原理：语法分析3-LR分析器

编译原理:LL(1),LR(0),SLR(1),LALR(1),LR(1)对比

《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析

Python栈实现

发表评论

表情：
评论列表 （有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

    相关 LL（1）文法 JAVA

    E文法表达式类 G 定义文法类 LL 文法分析类 ， 包含对First,Follow,Select集合的求解以及对表达式的分析函数  Main测试分析程序，并输出结果

    灰太狼灰太狼/ 0 赞/ 232 阅读

    相关 LL(1)文法

    文章目录 预测分析法的工作过程 S\_文法（简单的确定性文法） 什么时候使用$\\epsilon$产生式？ 非终结符的后继符号集 产生式的可

    川长思鸟来川长思鸟来/ 0 赞/ 396 阅读