private ItemSet CLOSUREItemSet I ItemSet J = new ItemSet; foreach var item in Iitems JitemsAdditem; StackItem stack = new StackItem; foreach Item i in Iitems stackPushi;
此代码实现了构建LR(1)自动机的过程。具体分析如下:
函数CLOSURE(ItemSet I):计算一个项目集的闭包。首先将原项目集中的所有项目添加到新的项目集J中,然后对于每个项目中dot后面是非终结符的情况,将该非终结符对应的每个产生式的第一个符号作为dot所指向的位置,新建一个项目加入到J中。最后返回闭包项目集J。
函数GOTO(ItemSet I, string X):计算一个项目集I关于符号X的goto操作后得到的新项目集。遍历I中的每个项目,对于dot后面是X的项目,新建一个项目,dot位置后移一位,加入到新项目集J中。最后返回闭包项目集J。
函数buildDFA():构建LR(1)自动机。首先构造初始项目集,即将 S'->S 作为第一个项目加入到一个项目集中,然后对该项目集求闭包,得到初始项目集。使用队列保存待处理的项目集,初始化状态编号和状态集合。依次对队列中的每个项目集I进行处理,计算I中每个符号的移进操作后得到的新项目集J,并将J加入到状态集合中。如果J不为空且还没有被加入到状态集合中,则将其加入到队列中。同时,记录每个状态到达其他状态的转移操作,并保存到transitions字典中。最后得到构建好的LR(1)自动机
原文地址: https://www.cveoy.top/t/topic/g8Hs 著作权归作者所有。请勿转载和采集!