如何手写语法分析器
http://www.cppblog.com/vczh/archive/2008/06/15/53373.aspx
如何手写语法分析器
陈梓瀚
华南理工大学软件05级本科
vczh@163.com
http://www.cppblog.com/vczh/
在写可配置的语法分析器之前,我觉得还是先说说如何手写语法分析器好。因为对于大部分人来说,开发一个可配置的语法分析器并没有什么作用,反而针对某种特定的语法开发特定的语法分析器是特别有必要的。典型的有表达式计算器、某种格式化的文件(HTML、XML等)或者是其他的复杂而且符合树型结构的字符串。根据目前论坛的反应来看,有一些朋友们对如何开发一套自己的脚本引擎比较感兴趣。等基础的文章都写完以后我会考虑撰写一个系列的文章介绍如何开发自己的脚本引擎。
这篇文章会附带一些必要的代码以便帮助读者们理解。为了方便,代码使用DevC++开发。
一、定义语法
在开发语法分析器之前,有必要讲一下语法的定义。这篇文章给出的是一个比较机械化的方法,掌握了这个方法之后手写语法分析器会变成一件没什么挑战性但是很麻烦的工作。因为设计起来太简单,但是代码很多。有些人为了连麻烦的工作也不要会去开发可配置的语法分析器。不过这里先不管这么多,首先给出一个比较使用的语法。
我们考虑一个经常从书上或者经常见到的例子:LISP语言。这门语言的表达式相当奇怪,操作符基本上当成函数处理,而且强迫用户给出优先级。因为LISP的操作符是没有优先级的。譬如(1+2)*(3+4)在LISP会被写成(* (+ 1 2) (+ 3 4) )。
让我们看一下这种语法的结构。括号内可以写很多个值,第一个被约定为是函数,之后的是参数。参数的个数是不确定的。一个函数调用的结果仍然是值,这就允许表达式进行嵌套。一个复杂一点的例子:2sinxcosx在LISP内被写成(* 2 (sin x) (cos x))。我们注意到最外层的乘法有3个参数,因此代表连乘。其次,(1)跟1的结果是一样的。
于是我们如何规定这种表达式的语法呢?我们可以给出若干条。为了方便我们去掉LISP语言允许的curry属性,也就是说(+ 1 2)等价于( ( (+) 1) 2)。
1、 数字可以为值
2、 一个值可以构成参数列表,参数列表后紧接着一个值仍然是参数列表
3、 表达式可以为值,或者是括号内包含操作符或函数名外加可选的参数列表
于是我们可以使用一种形式化的方法来写出这个表达式。首先我们可以为表达式命名,譬如表达式我们使用expression或者exp等。其次name=rule代表复杂的rule将会使用一个名字name来代替。最后,a b代表a之后紧接着b。
这样的话,我们就可以使用一种比较简洁的方法来表示上面提到的简化后的LISP表达式语法:
Operator=”+”
Operator=”-“
Operator=”*”
Operator=”/”
Expression=<数字>
Expression= “(” Operator Expression Expression “)”
Expression=“(”Expression “)”
这样写的话觉得很烦,我们可以追加多两种定义语法的语法:
1、A | B代表A或者B都可以,并且如果字符串被A匹配成功的话将不会考虑B
2、[ A ]代表A是可以存在或者不存在的,但是尽量使其存在
于是我们可以把上面的语法改写成如下形式:
1) Operator=”+” | “-” | “*” | “/”
2) Expression=<数字> | “(“ Expression “)” | “(“ Operator Expression Expression “)”
第一条语法规则说的是Operator,也就是操作符,可以是加号、减号、乘号或者除号。第二条语法规则说的是一条表达式可以只由数字构成、一个加了括号的表达式或者一个加上了括号的操作符和两个参数。
二、根据语法写代码
到了这里,我们可以考虑一下如何通过语法组织我们的代码了。上面的语法并没有包含如何去除空格的语法,这个事情语法表达只会徒增烦恼,因此我们自己解决可能会更好一点。在语法分析的时候,我们都是一点一点读入字符串的,因此我们的函数的的形式大概如下:
·读入字符串,返回结果或者错误信息
·如果没有错误的话,则将字符指针偏移到尚未读取的位置
·如果有错误的话,保持字符指针不变
好了,现在我们来看第一条语法。我们需要一个方法来检查输入是否由我们需要的字符串开头,当然这里仍然需要考虑空格的问题。我们可以写一个函数,输入字符指针和一个字符串。这个函数先过滤掉空格然后检查剩下的地方是不是由指定的字符串开始的。正确的话返回true并将输入的字符指针往后诺到尚未读取的地方:
/*
检查Stream的前缀是否Text
是返回true并将Stream偏移strlen(Text)个字符
否则返回false
此函数会过滤Stream开头的空格
*/
bool Is(char*& Stream , const char* Text)
{
size_t len=strlen(Text);
/*保存参数*/
char* Read=Stream;
/*过滤空格*/
while(*Read==' ')Read++;
if(strncmp(Read,Text,len)==0)
{
Stream=Read+len;
return true;
}
else
{
return false;
}
}
代码很短我就不解释了。当然,有了这个函数之后我们可以很轻松地写出一个判断字符串是否由操作符开头的函数:
/*
检查Stream是否操作符
是的话返回操作符的字符并将Stream偏移至操作符之后
否则返回
*/
char IsOperator(char*& Stream)
{
/*A||B操作符的特性是如果A==true则不对B求值
所以表达式会在一个检查成功后停下来
*/
if(Is(Stream,"+") || Is(Stream,"-") || Is(Stream,"*") || Is(Stream,"/"))
{
/*此时操作符已经被越过,所以返回Read[-1]*/
return Stream[-1];
}
else
{
return 0;
}
}
第一条语法到了这里就结束了。然后我们考虑第二条语法。这条语法判断一个字符串是否表达式,首先判断一个字符串是否数字,失败的话再检查是否由括号打头。因此我们需要一个判断字符串是否由数字开头。这里我们先引进一个struct:
/*表达式分析结果*/
struct Expression
{
int Result; /*表达式结果*/
char* Error; /*错误信息,没有错误则为*/
char* Start; /*错误的位置*/
};
这个Expression结构用于表达字符串的分析结果。Result是表达式的计算结果,Error如果非0则保存了错误信息,此时Start保存了错误信息在字符串的什么地方被引发。有了这个Expression之后我们就可以写出如下判断字符串是否由数字开头的函数了。为了方便,这个函数只判断非负整数。
/*
检查Stream是否数字,是的话则将Stream偏移到数字之后
*/
Expression GetNumber(char*& Stream)
{
/*font-size: 9pt; color:
分享到:
相关推荐
JavaScript语法分析器是一种用于解析JavaScript源代码的工具,它能够将源代码分解成一系列符合语法规则的结构,这些结构通常被称为语法树或抽象语法树(AST)。在本项目中,这个语法分析器是基于LL(1)文法构建的,...
编译原理-递归下降语法分析器源代码,手写有注释,能打印出语法树,进行部分错误处理,dev c编写,所有内容皆由一个cpp文件实现
编写一个语法分析器,特别是对初学者而言,是一个学习编程语言解析原理和实现过程的好方法。语法分析器的主要任务是解析输入的文本,将其转化为计算机可以理解的抽象语法树(AST)。在这个过程中,我们需要定义语法...
在这个实验中,学生需要实现一个语法分析器,能够正确地分析符号流,并生成对应的AST。 语义分析是编译器的第三阶段,负责对抽象语法树进行语义分析,以确保源代码的语义正确性。在这个实验中,学生需要实现一个...
此外,为了支持十几种语言的语法高亮,你可能需要集成现有的开源库,如JFlex(用于词法分析)、CUP(用于语法分析)或JTextComponent的扩展,如RSyntaxTextArea,它已经内置了多种语言的语法高亮支持。 总的来说,...
该算法的主要思想是:如果栈顶的终结符和下一个输入符之间的优先关系是<或=,则语法分析器移动,表示还没有发现句柄的右端;如果是>关系,就调用归约。 三、算符优先分析法优缺点 算符优先分析法的优点是速度快,...
8. **与语法分析的交互**:词法分析器产生的标记会被送到语法分析器,进行语法规则的匹配。两者之间的接口设计也很重要,通常通过一个包含标记类型和值的数据结构来传递信息。 9. **词法分析器2.0**:这个版本可能...
2. **词法分析器实现**:可能使用了某种特定的词法分析工具或方法,如手写词法分析器,或是使用 Lex/Yacc、Flex/Bison 等工具生成词法分析器。这部分会解释如何构建和配置这些工具,以及如何定义和测试词法规则。 3...
《基于LEX的语言词法分析器》 在计算机科学领域,编译原理是研究如何将...此外,亲手实现词法分析器也能帮助理解编译器其他阶段(如语法分析、语义分析和代码生成)的工作流程,从而全面提高编程技能和软件开发能力。
在实际应用中,词法分析器经常与语法分析器配合工作,共同完成源代码的解析,为编译或解释过程奠定基础。 理解词法分析对于学习编程语言的编译原理至关重要,也是软件工程专业学生必修的一门课程。通过分析“ccc....
用户可以通过拖拽、选择预设操作等方式,快速构建复杂的SQL查询语句,而无需记忆或手写繁琐的SQL语法。这对于初学者和经验丰富的开发者来说,都是一个极大的便利。 其次,该分析器具备多种数据库支持能力,可以适应...
1. 图像处理:首先,手写字符被捕捉为图像,通过扫描仪或摄像头输入到计算机。图像预处理是关键步骤,包括灰度化、二值化、噪声去除等,以提高后续识别的准确性。 2. 特征提取:在图像处理后,需要对手写字符进行...
"VIP",全称可能为"Very Important Programming",是一个小型语言,它具有完整的语言处理流程,包括手写词法分析器、解析器、编译器和自定义字节码解释虚拟机(VM)。这样的设计使得VIP语言能够高效地运行和解释代码...
在C#中,词法分析器会识别出如`int`、`if`、`MyVariable`等不同的token。 2. **语法分析**:接着,编译器进行语法分析,根据语言的语法规则(通常用BNF或EBNF表示)将词法单元组合成抽象语法树(AST)。AST是程序...
在构建词法分析器时,开发者可能会使用诸如Flex(一种词法分析器生成器)或者直接手写C++代码的方式来实现。Flex会根据用户提供的正则表达式生成词法分析器的C++代码,而手写则需要开发者自己实现状态机逻辑。 总的...
然后,你需要编写一个解析器,这个解析器将SQL语句分解成解析树或抽象语法树(AST),这是一个表示语法结构的数据结构。 解析完成后,接下来的步骤是将这些解析结果转化为关系表达式。关系表达式通常包含变量、常量...
Windows系统自带的记事本(Notepad)可以用来创建文本文件,但更专业的汇编编辑器如NASM(Netwide Assembler)或MASM(Microsoft Macro Assembler)能提供语法高亮和更方便的功能。使用这些工具,我们可以编写汇编源...
MATLAB因其丰富的图像处理工具箱和易读易写的语法,成为了进行此类任务的理想选择。 首先,我们需要了解手写数字识别的基本流程。这通常包括以下几个步骤: 1. 图像预处理:获取的手写数字图像可能存在噪声、不...