可配置语法分析器开发纪事（六） 构造一个真正能用的状态机（下）

上一篇文章对大部分文法都构造出了一个使用的状态机了，这次主要来讲右递归的情况。右递归不像左递归那么麻烦，因为大部分右递归写成循环也不会过分的让语法树变得难以操作，不过仍然有少数情况是我们仍然希望保留递归的语法树形状，譬如C++的连等操作，因此这里就来讲一下这个问题。

右递归是怎么形成的呢？在这里我们先不想这个问题，我们来看一个普通的文法。在上一篇文章我们已经说过了，如果一条文法有一个非终结符引用了另一条文法，那么就要做一条shift和reduce来从这个状态机穿插到那个状态机上：

开发纪事（六） 构造一个真正能用的状态机（下）-语法树构造">

在这里需要讲一下，绿色的箭头是shift，紫色的箭头是reduce，他们都是ε边。更进一步说，如果A刚好以B作为结尾，那么A的最后一个输入就不是终结符输入，不过因为她不是右递归，所以现在看起来还没什么问题：

我们已经接近右递归的形状了。右递归的一个根本特征当然是递归（废话）。为了制作一个右递归，我们可以想一下，如果A和B不是两个rule而是同一个rule会怎么样？当然咋这么一看，好像就是A可以访问自己了：

时间： 2024-11-08 18:59:45

可配置语法分析器开发纪事（六） 构造一个真正能用的状态机（下）的相关文章

可配置语法分析器开发纪事（二） 构造符号表

上一篇博客讲到了构造语法树的问题.有朋友在留言问我,为什么一定要让语法分析器产生语法树,而不是让用户自己决定要怎么办呢?在这里我先解答这个问题. 1.大部分情况下都是真的需要有语法树 2.如果要直接返回计算结果之类的事情的话,只需要写一个visitor运行一下语法树就好了,除去自动生成的代码以外(反正这不用人写,不计入代价),代码量基本上没什么区别 3.加入语法树可以让文法本身描述起来更简单,如果要让程序员把文法单独放在一边,然后自己写完整的语义函数来让他生成语法树的话,会让大部分情况(需要语法

可配置语法分析器开发纪事（一） 构造语法树

就像之前的博客文章所说的,(主要还是)因为GacUI的原因,我决定开发一个更好的可配置轻量级语法分析器来代替之前的落后的版本.在说这个文章之前,我还是想在此向大家推荐一本<编程语言实现模式>,这的确是一本好书,让我相见恨晚. 其实说到开发语法分析器,我从2007年就已经开始在思考类似的问题了.当时C++还处于用的不太熟练的时候,难免会做出一些傻逼的事情,不过总的来说当年的idea还是能用的.从那时候开始,我为了锻炼自己,一直在实现各种不同的语言.所以给自己开发一个可配置语法分析器也是在所难免的

可配置语法分析器开发纪事（五） 构造一个真正能用的状态机（中）

上一篇博客写到了如何给一个非终结符的文法规则构造出一个压缩过的下推状态机,那么今天说的就是如何把所有的文法都连接起来.其实主要的idea在(三)和他的勘误(三点五)里面已经说得差不多了.但是今天我们要处理的是带信息的transition,所以还有一些地方要注意. 所以在这里我们先把几条文法的最后的状态机都列出来(大图): 开发纪事(五) 构造一个真正能用的状态机(中)-语法树构造"> 本栏目更多精彩内容:http://www.bianceng.cn/Programming/cplus/

可配置语法分析器开发纪事（四） 构造一个真正能用的状态机（上）

本来说这一篇文章要把构造确定性状态机和look ahead讲完的,当我真正要写的时候发现东西太多,只好分成两篇了.上一篇文章说道一个基本的状态机是如何构造出来的,但是根据第一篇文章的说法,这一次设计的文法是为了直接构造出语法树服务的,所以必然在执行状态机的时候就要获得构造语法树的一切信息.如果自己开发过类似的东西就会知道,类似LALR这种东西,你可以很容易的把整个字符串分析完判断他是不是属于这个LALR状态机描述的这个集合,但是你却不能拿到语法分析所走的路径,也就是说你很难直接拿到那颗分析树.没

可配置语法分析器开发纪事（三） 生成下推自动机

上一篇博客讲到了构造符号表的事情.构造完符号表之后,就要进入语义分析的后一个阶段了:构造状态机.跟我以前写的如何实现正则表达式引擎的两篇文章讲的一样,自动机先从Epsilon Nondeterministic Automaton开始,然后一步一步构造成Deterministic Automaton.但是语法分析和正则表达式有很大不同,那么这个自动机是什么样子的呢? (对学术感兴趣的人可以去wiki一下"下推自动机") 下推自动机和有限自动机的区别是,下推自动机扩展成普通的自动机的时候,

可配置语法分析器开发纪事（三点五） 生成下推自动机的具体步骤

刚刚发了上一篇文章之后就发现状态机画错了.虽然LiveWriter有打开博客并修改文章的功能,不过为了让我留下一个教训,我还是决定发一篇勘误.这个教训就是,作分析的时候不要随便"跳步",该一步一步来就一步一步来.其实人呢,就是很容易忘掉以前的教训的了.第一个告诉我不能这么干的人其实是小学三年级的数学老师.当时我因为懒得写字,所以计算应用题的时候省了几步,被批评了. 故事就从状态机开始.文法我就不重复了,见上一篇文章.现在我们从状态机开始.第一个状态机是直接从文法变过来的: 开发纪事(三

求教：Eclipse如何为新语言配置语法高亮？

问题描述 一个很小众的编程语言,想尝试用Eclipse作为IDE,有关键词若干,希望实现语法高亮和代码提示.请问该如何配置?小弟新手上路,请予指教,烦请讲详细一点.谢谢先 解决方案 解决方案二:eclipse语法提示(红色波浪线)如何开启关闭设置步骤:windows-->perferences-->editors-->texteditor-->annotation在里面选择errors,把其中的三个选项都勾上就可以啦代码提示按alt+/实现语法高亮是系统自带的,不用设置解决方案三:

利用Stripes、Apache Derby和Eclipse进行无配置的J2EE开发（二）

Stripes 注释和单元测试 发现 Stripes 注释的套件,并在您的应用程序上构造单元测试. Stripes 注释 Stripes 带有以下注释: 分派注释: @UrlBinding:该注释允许 ActionBean 类生成定制 UrlBinding URL 路径.在带注释 的 UrlBinding 路径被请求时,会调用 ActionBean 类. @HandlesEvent:该绑定允许通过指定的名称调用 actionBean() 方法.默认情况下, Stripes 试图将事件名解析成 a

WCF分布式开发步步为赢(3)WCF服务元数据交换、配置及编程开发

今天我们继续WCF分布式开发步步为赢(3)WCF服务元数据交换.配置及编程开发的学习.经过前面两节的学习,我们了解WCF分布式开发的相关的基本的概念和自定义宿主托管服务的完整的开发和配置过程.今天我们来详细学习WCF服务元数据交换的相关内容.WCF服务元数据究竟是什么?为什么WCF服务要暴露元数据交换节点?这些和以前的Web Service有什么关系?WCF服务元数据交换的方式有那些?我们如何实现WCF服务元数据交换,本节我们会详细讲解.全文结构如下:[1]WCF服务元数据的基本概念.[2]WC