yacc语法

语法分析程序自动产生器yacc的使用方法2.l yacc概述形式语言都有严格定义的语法结构，我们对它们进行处理时首先要分析其语法结构。

yace 是一个语法分析程序的自动产生器，严格地说Lex也是一个形式语言的语法分析程序的自动产生器。

不过Lex所能处理的语言仅限于正规语言，而高级语言的词法结构恰好可用正规式表示，因此Lex只是一个词法分析程序的产生器。

yace可以处理能用LALR（1）文法表示的上下文无关语言。

而且我们将会看到yace具有一定的解决语法的二义性的功能。

yacc的用途很广，但主要用于程序设计语言的编译程序的自动构造上。

例如可移植的C 语言的编译程序就是用yacc来写的。

还有许多数据库查询语言是用yacc实现的。

因此，yacc 又叫做“编译程序的编译程序（"A Compiler ComPiler"）。

yacc的工作示意图如下；图2.1 yacc示意图在图2.1中，“yacc源程序”是用户用yacc提供的一种类似BNF的语言写的要处理的语言的语法描述。

yacc会自动地将这个源程序转换成用LR方法进行语法分析的语法分析程序yyparse，同Lex一样，yacc的宿主语言也是C，因此yyParse是一个C语言的程序，用户在主程序中通过调用yyparse进行语法分析。

语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还需要有一个词法分析程序与它配合工作。

yyparse要求这个词法分析程序的名字为yylex。

用户写yylex时可以借助于Lex。

因为Lex产生的词法分析程序的名字正好是yylex，所以Lex与yacc配合使用是很方便的，这将在2.5的2.5.3中详细介绍，请注意词法分析程序也是可以包含在yacc 源程序中的。

在yacc源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它们进行归约时要完成的语义动作，语义动作是用C语言写的程序段。

语法分析的输出可能是一棵语法树，或生成的目标代码，或者就是关于输入串是否符合语法的信息。

词法分析程序的自动生成系统LEX和语法分析程序自动生成系统YACC介绍如何采用形式化的方法描述程序设计语言字母表即符号（字符、元素）的非空有穷集合。

符号的有穷序列称为符号串。

称为空符号串，用ε表示。

空集合Φ的正闭包表示A上元素a,b构成的所有符号串的集合,集合A的闭包比集合A的正闭包多含一个空符号串 。

形式语言：当语言为无穷集合时，用文法来描述语言。

当语言为有穷集合时，用枚举法来表示语言。

规则也称产生式每个非终结符号表示一定符号串的集合，用大写字母表示或用尖括号把非终结符号括起来。

文法的开始符号或文法的识别符号.直接推导用式子，文法，枚举描述语言最左推导和最右推导对于无二义性的语言唯一吗？定于的语言为：短语的定义是相对于句型和非终结符而言的也就是说，是这个句型中最左边的非终结符所得到直接短语。

只能置换一个非终结符，得到句型。

置换非终结符的串即为短语。

如果是规则的右部则为直接短语。

再从直接短语中找出句柄。

这样可以直接从推到式看出来。

这样短语一定是句型的子串语法树，推导树？？？？？？？？？？？？？？？？？？？？？？？？？？即是，句型上某一个子树形成的句型子串即为其短语。

其直接父节点，所形成的句型子串即为直接短语。

最左的为句柄。

可以从树根开始往下找，可以找出全部短语。

二义性的定义是，某个句子存在两棵不同的语法树或者两个不同的最左（最右）推导。

3型文法定义的语言为3型语言：右线性文法，右部为非终结符在右边，右边为终结符的正闭包或者为非终结符的闭包。

注意A->ε也是3型文法。

A->abcdefB也是3型文法。

即左部位单个非终结符，注意A->ε也是2型文法，看清楚每个集合括号里面的东西。

yacc 中的优先级声明
在Yacc（Yet Another Compiler Compiler）中，优先级声明用于指定语法规则的优先级。

优先级高的规则将优先匹配输入的符号序列。

Yacc 中的优先级声明使用 %left、%right 和 %nonassoc 关键字来指定。

1.%left：指定左侧优先级。

这意味着在该规则中的符号将优先匹配输入的
符号序列。

例如：
这表示加号和减号具有相同的优先级，它们将优先匹配输入序列中的符号。

2.%right：指定右侧优先级。

这意味着在该规则中的符号将延迟匹配输入的
符号序列，直到左侧的规则都匹配完毕。

例如：
这表示加号和减号具有相同的优先级，它们将延迟匹配输入序列中的符号，直到左侧的规则都匹配完毕。

3.%nonassoc：指定非关联优先级。

这意味着在该规则中的符号将不与其他
符号进行关联匹配，即它们不能与左侧或右侧的符号一起组成更大的表达式。

例如：
这表示等号具有非关联优先级，它不能与其他符号一起组成更大的表达式。

在Yacc 中，优先级的高低决定了符号匹配的顺序。

高优先级的规则将优先匹配输入序列，而低优先级的规则将在高优先级规则匹配完毕后进行匹配。

如果两个规则具有相同的优先级，则按照它们在Yacc 文件中出现的顺序进行匹配。

yacc(Yet Another Compiler Compiler)，是一个经典的生成语法分析器的工具。

是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。

yacc生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。

yacc本来只在Unix系统上才有，但现时已普遍移植往Windows 及其他平台。

分析程序生成器(parser generator)是一个指定某个格式中的一种语言的语法作为它的输入，并为该种语言产生分析过程以作为它的输出的程序。

在历史上，分析程序生成器被称作编译-编译程序( compiler- compiler )，这是由于按照规律可将所有的编译步骤作为包含在分析程序中的动作来执行。

现在的观点是将分析程序仅考虑为编译处理的一个部分，所以这个术语也就有些过时了。

合并 LALR(1) 分析算法是一种常用的分析生成器，它被称作 Yacc( yet another compiler- compiler )。

给出 Yacc 的概貌来，将使用Yacc为 TINY 语言开发一个分析程序。

作为 Yacc 对说明文件中的 %token NUMBER 声明的对应。

Yacc 坚持定义所有的符号记号本身，而不是从别的地方引入一个定义。

但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。

yacc的输入是巴科斯范式（BNF）表达的语法规则以及语法规约的处理代码，Yacc输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。

yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

Yacc最初由AT&T的Steven C. Johnson为Unix操作系统开发，后来一些兼容的程序如Berkeley Yacc，GNU bison，MKS yacc和Abraxas yacc陆续出现。

Lex和Yacc⼊门教程（⼋）.使⽤堆栈编译语法Lex和Yacc⼊门教程(⼋).使⽤堆栈编译语法分类： C++/C/C# 2007-06-05 11:08 4571⼈阅读评论(26) 收藏举报yacccommandshellunix存储linuxLex和Yacc应⽤⽅法(⼋).使⽤堆栈编译语法草⽊⽠ 20070604⼀、序前⾯⼀些系列⽂章着重介绍了递归语法树在编译理论⽅⾯的应⽤。

本⽂则会介绍另⼀种实现⽅式----堆栈。

堆栈在底层系统有⼗分⼴泛的应⽤，同样也⼗分擅长处理语法结构，这⾥通过实际⽰例探讨如何构造堆栈完成语法分析。

重要补充：下⾯是本系列⽂章全⽰例代码统⼀的调试测试环境，另对于lex,yacc⽂件需要存储为Unix格式，这⼀点和Linux，Unix下shell很类似，DOS格式的Shell是不能够被执⾏的，同样bison,lex编译DOS格式⽂件会出错误提⽰：Red Hat Linux release 9 (Shrike)Linux 2.4.20-8gcc version 3.2.2 20030222bison (GNU Bison) 1.35lex version 2.5.4flex version 2.5.4⼆、具体⽰例本⽰例主要完成功能：1 ⽀持整型，浮点型和字符串型2 ⽀持变量存储，变量名可为多个字符3 ⽀持整型，浮点型的+-*/()=运算法则4 ⽀持字符串型赋值5 ⽀持print打印整型，浮点型和字符串型6 ⽀持打印变量值7 ⽀持while if else switch四种控制结构，并⽀持控制结构的嵌套8 ⽀持> >= < <= != == 六种⽐较运算，同时也⽀持字符串的⽐较9 ⽀持 && || 复合⽐较运算10 ⽀持对空格和TAB的忽略处理11 ⽀持#的单⾏注释12 ⽀持{}多重组合13 ⽀持编译错误的具体显⽰14 ⽀持外部变量值传⼊(整型，浮点型和字符型)15 ⽀持外部变量获取(整型，浮点型和字符型)16 完整的企业应⽤模式三、⽰例全代码(略)A.stack.l----------------------------------------------B.stack.y----------------------------------------------C.stack.h----------------------------------------------D.stackparser.c----------------------------------------------E.public.h----------------------------------------------F.main.c----------------------------------------------G.mk 编译shell⽂件----------------------------------------------bison -d stack.ylex stack.lgcc -g -c lex.yy.c stack.tab.c stackparser.car -rl stack.a *.ogcc -g -o lw main.c stack.aH.mkclean shell⽂件----------------------------------------------rm stack.tab.crm stack.tab.hrm lex.yy.crm *.orm *.arm lw四、思路说明上⾯列出的代码是⽬前最长的。

使用Yacc生成语法分析程序1、创建空工程File菜单下选择New：弹出下面对话框：选择Win32 Console Application，同时在Project Name下输入工程名字：ParserByYacc点击Ok按钮，弹出下面对话框：不做任何选择，按照默认“An empty project”，直接点击Finish按钮，弹出下面对话框：直接点击OK按钮，工程创建完毕。

2、使用Yacc生成语法分析程序点击“开始”，在“开始”菜单中选择“运行”，如下图所示在弹出的对话框中敲入cmd，启动DOS窗口使用DOS命令切换到E:\ ParserByYacc将yacc.exe文件拷贝到ParserByYacc工程下：将编写好的TINY.Y文件拷贝到ParserByYacc工程下：运行yacc生成y.tab.c和y.tab.h文件：3、添加文件首先在windows环境下，把设计好的文件GLOBALS.H、MAIN.C、SCAN.C、SCAN.H、PARSE.H、UTIL.C 和UTIL.H拷贝到ParserByYacc工程下：如图所示，选中Project菜单，选择下面Add To Project子菜单下面的Files子菜单：点击后弹出对话框：选中的刚拷贝进来的文件和Yacc生成的文件，点击OK按钮：在左侧的工程文件列表中，可以清楚地看到这些文件：4、生成可执行文件编译生成可执行文件ParserByYacc.exe在本工程的debug目录下：为了验证本语法分析程序的运行结果，把样本程序SAMPLE.TNY拷贝到可执行程序所在的目录下：5、验证运行结果Windows环境下点击“开始”，选中其中的“运行(R)”弹出下面对话框，输入cmd命令：输入上图所示的类似命令，进入可执行程序所在目录。

在当前目录下输入命令：ParserByYacc sample.tny，然后回车，则得到相应的运行结果：。

实验2.4 学习YACC并构造简单语法分析程序一、实验目的1. 学习使用辅助软件YACC2. 理解语法分析程序的构造原理二、实验内容构造一个PL/0程序的命令行简易版本程序，要求具有变量和常量定义语句Var和Const，具有基本输入输出语句Read 和Write,包含基本的算术运算+ 、-、*、/ 和( ) 运算，语句以分号（；）结束,整个程序以END结束。

1. 学习YACC语法的使用具体内容可参考课本附录2. 使用LEX构造词法分析程序yylex.c示例代码:\+ {return '+';}\* {return '*';}":=" {return BECOMES;}\, {return ',';}\; {return ';';}V AR|var {return V AR;}[a-zA-Z][a-zA-Z0-9]* {strcpy(yylval.str,yytext);return IDENT;}3. 使用YACC构造语法分析程序构造符合YACC语法的程序PL0.YACPL0.YAC示例代码:%union {char str[MAXSTRLEN];int num;}%token V AR CONST READ WRITE EXIT BECOMES%token <num> NUMBER%token <str> IDENT%type <num> number%type <str> ident%type <num> expression%left '+' '-'%left '*' '/'%left UMINUS%%begins : /*empty*/| begins program;program : var_state ';'| const_state ';'| statement ';'| error ';'{};var_state : VAR var_list{};var_list : a_var_list| var_list ',' a_var_list{};a_var_list : ident{ i=position($1);if (i) printf("Error: variable (%s) already defines \n",$1);else { if (tx==MAXTABLESIZE)printf("Error: table full(only%d numbers) ,varible define error \n",MAXTABLESIZE);else {strcpy(table[tx].name,$1);table[tx].kind=V ARLABEL;printf("variable (%d):%s successfullt defined.\n",tx,$1);tx++;}}};statement : write_state| read_state| value_state| exit_state ';'write_state: WRITE '(' write_list ')'{ if (debug) printf("(write_statement finished)\n");};write_list : a_write| write_list ',' a_write;a_write : expression{ printf("%d\n",$1);}%%#include "lexyy.c"int yyparse();main(){return yyparse();}4. 生成目标代码并运行1) 生成C语言源程序在DOS 命令提示符下运行Y ACC.exeYACC pl0.yac产生C语言代码pl0.C2）进入TC集成环境将.C文件编译产生可执行文件.EXETC pl0.C3）在DOS 命令提示符下执行生成的pl0.exe输入程序示例如下:Const a =3 ;Var b,c ;Read(b);c := a + b ;Write(c) ;END.三、实验报告按照语法分析的原理，给出借助Y ACC自动生成语法分析器的过程描述，和生成的语法分析程序是如何运作的。

yacc 语法树定义解析好呀，以下是为您创作的关于【yacc 语法树定义解析】的科普文章：当我们谈到“yacc 语法树定义解析”时，可能您的脑袋里会冒出一堆问号：这是啥？听起来好复杂！别担心，让我们用一个有趣的类比来开始这场知识之旅。

想象一下，您正在建造一座城堡。

每一块砖头、每一根木材、每一扇窗户都有它特定的位置和作用。

这些建筑材料就像是编程语言中的各种元素，比如关键字、变量、运算符等等。

而语法树呢，就像是这座城堡的设计蓝图。

它清晰地展示了这些元素是如何组合在一起，形成一个有结构、有逻辑的整体。

那到底什么是 yacc 语法树定义解析呢？简单来说，yacc 是一个工具，它能帮助我们根据特定的语法规则，把我们编写的程序代码转化为一棵像城堡蓝图那样的语法树。

这棵树的每个节点就代表了代码中的一个元素，节点之间的连接则表示它们之间的关系。

比如说，在一个简单的数学表达式“2 + 3 * 4”中，通过 yacc 进行语法树定义解析后，可能会形成一个这样的结构：根节点是整个表达式，下面有一个加法节点，加法节点的左边是数字 2，右边是一个乘法节点，乘法节点的左边是数字 3，右边是数字 4。

那这玩意儿在实际中有啥用呢？让我们来瞧瞧。

假设您是一个网页开发者，要编写一个能够处理用户输入的表单验证程序。

用户可能会输入各种各样的内容，比如电话号码、邮箱地址等等。

通过 yacc 语法树定义解析，您可以轻松地定义一套规则，来检查用户输入是否符合您设定的格式要求。

就好像您在城堡门口设置了卫兵，只有符合规定的“材料”才能进入城堡。

再比如说，编译器在把我们写的高级语言（比如 C 语言、Java 语言）转换成机器能理解的低级语言时，也会用到 yacc 语法树定义解析。

它能够帮助编译器更好地理解我们的代码意图，进行优化和错误检查。

这就像是一个精明的管家，把城堡里的一切都安排得井井有条，确保没有任何混乱和错误。

在自然语言处理中，yacc 语法树定义解析也能大显身手。