简要介绍 构造抽象语法树是构造基于DFA的正则表达式引擎的第一步。目前在我实现的这个正则表达式的雏形中，正则表达式的运算符有3种，表示选择的|运算符，表示星号运算的*运算符，表示连接的运算符cat（在实际正则表达式中被省去）。例如对于正则表达式a*b|c，在a*和b之间省略了连接运算符cat。其中|、cat运算符是双目运算符，*运算符是单目运算符。下图来自编译原理一书：...
2013-12-06 22:47 阅读(20) 评论(0) 说明：本系列文章介绍的算法均来自编译原理（龙书）一书，如果读者对代码没有兴趣，只想了解算法思路，完全可以阅读龙书相关章节内容，比我讲得清晰透彻。序： 啃编译原理半年以来，任然徘徊在前4章，其间反反复复，时而不求甚解，时而略有所悟。后来接触到正则表达式，对其实现原理颇有兴趣，于是百度之、谷歌之，以求解惑。先是搜索到不少国内发表的学术论文和各位大侠博客上的文章，后又通...
2013-12-06 22:46 阅读(24) 评论(0) 一、状态机描述状态机理论最初的发展在数字电路设计领域。在数字电路方面，根据输出是否与输入信号有关，状态机可以划分为Mealy型和Moore型状态机；根据输出是否与输入信号同步，状态机可以划分为异步和同步状态机。而在软件设计领域，状态机设计的理论俨然已经自成一体。Moore型状态机的输出只和当前状态有关，和输入无关，如果在软件设计领域设计出这种类型的状态机，则该状态机接受的事件都是无内蕴信息的事...
2013-12-06 14:27 阅读(23) 评论(0) 陈梓瀚 vczh@163.com http://www.cppblog.com/vczh/1、问题概述随着计算机语言的结构越来越复杂，为了开发优秀的编译器，人们已经渐渐感到将词法分析独立出来做研究的重要性。不过词法分析器的作用却不限于此。回想一下我们的老师刚刚开始向我们讲述程序设计的时候，总是会出一道题目：给出一个填入了四则运算式子的字符串，写程序计算该式子的结果。除此之外，我们有...
2013-12-06 14:15 阅读(21) 评论(0) Bison功能很强大，可以加参数-v可以生成可阅读的.output文件，还可以生成dot转换图本文以lex yacc 创建一个桌面计算器 为例子研究bison生成代码所有介绍都以bison生成为准，通过-v生成*.output文件，通过设置#define YYDEBUG 1以及yydebug=1进行调制文法0 ACCEPT : OVER1 OVER : E '\n'2...
2013-11-26 23:16 阅读(26) 评论(0) 语法分析使用Bison，在前面的博文中提到一些如何在Windows下安装Bison，但是从语法分析开始，我还是在Linux下写实验的，安装了ubuntu，因此需要在Linux下安装Bison，这个安装是比较简单的，只需要在命令行中敲入如下命令：sudo apt-get install bison，同样，安装Flax：sudo apt-get install flex 如，写好...
2013-11-26 23:14 阅读(42) 评论(2) 什么是YACC？ yacc(Yet Another Compiler Compiler)，是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）. 使用巴克斯范式(BNF)定义语法，能处理上下文无关文法(context-free)。出现在每个产生式左边(left-hand side：lhs)的符号是非终端符号，出现在产生式右边(right-hand side：rhs)的符...
2013-11-26 23:13 阅读(27) 评论(0) 由于 目前的主要工作是IDE，而IDE中主要负责Compiler & Assembler部分，这两部分中都会用到flex & bison(Lex & Yacc)，所以通常的做法是在相应工程目录(如：工程为SDCC Compiler)下建立一个parser的目录，然后里面存放.l(lex文件)和.y(yacc文件)文件，还有一个.bat文件，这个.bat文件的作用是把.l和.y文件调用flex &...
2013-11-26 23:12 阅读(24) 评论(0) Bison适合上下文无关文法（Context-free grammar），并采用LALR(1)算法的文法。当bison读入一个终结符（token），它会将该终结符及其语意值一起压入堆栈。这个堆栈叫做分析器堆栈（parser stack）。把一个token压入堆栈通常叫做移进（shifting）；当已经移进的后n个终结符和组（groupings）与一个文法规则相匹配时，会被根据那个规则结合起来叫做归...
2013-11-26 23:12 阅读(20) 评论(0) 20050620 GNU Bison 中文手册翻译完成GNU Bison实际上是使用最广泛的Yacc-like分析器生成器,使用它可以生成解释器,编译器,协议实现等多种程序. 它不但与Yacc兼容还具有许多Yacc不具备的特性.这个手册编写十分完整,带你领略Bison在使用中的各个细节(注：并不是实现细节).如果发现错误,语句不通顺,意思不明,确请立即发邮件把您的建议或者您认为正确的翻...
2013-11-26 23:11 阅读(46) 评论(0) 最近由于项目需要，看了点关于编译原理和编译器等方面的资料，特别是词法分析和语法分析部分，现做一下小结。 一、编译器及其工作流程 编 译器，是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能识别，运行的低级机器语言的程序。编译器将源程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序。源程序一般...
2013-11-26 23:07 阅读(34) 评论(0) 1、概述 Lemon是一个LALR(1)文法分析器生成工具。虽然它是SQLite作者针对SQLite写的一个分析器生成工具，但是它与bison和yacc类似，是一个可以独立于SQLite使用的开源的分析器生成工具。而且它使用与yacc(bison)不同的语法规则，可以减少编程时出现错误的机会。Lemon比yacc和bison更精致、更快，而且是可重入的，也是线程安全的——这对于支持多线程的程...
2013-11-26 23:06 阅读(29) 评论(0) 本文为原创，部分bat代码来自熊春雷前辈的博文：http://blog.csdn.net/pandaxcl/archive/2006/07/04/873898.aspx 为什么要使用lex和yacc 最近的项目需要写一个Language Service，于是不可避免的涉足到了lex和yacc。lex和yacc原本是UNIX系统下的两个工具，用于编写涉及文本分析的程序。在Lin...
2013-11-26 23:04 阅读(35) 评论(0) 如题，本文主要是flex与bison 的配合问题。 bison设置在bison用户手册中已经详尽说明了，这里不再赘述。 主要说明一下flex 的设置，并给出一个示例工程。1. flex设置 %{/* 由于flex在输入结束时默认的yyterminate()返回值为0,与bison中token::END可以能不一致 */#define yyterminate() return tok...
2013-11-26 23:02 阅读(23) 评论(0) 我在VC下安装VC助手(VisualAssistX)， 让它可以高亮显示C/C++语法，同时支持快捷跳转、自动联想、简单重构等功能。1. 将flex的输入文件命名为后缀 .cpp， 但是将这个.cpp文件从工程编译中排除，这样既可以方便在flex输入文件中写C/C++代码。同时编译也不会报错。 2. 如果要让flex生成的头文件和源文件具有自己的名字，也很简单，在flex的输入文件中使...
2013-11-26 23:01 阅读(27) 评论(0) 
