用扩展的bnf表示法怎么消除文法左递归

你说的应该是编译原理吧。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成

一：带回溯的分析方法。

二：不带回溯的递归子程序（递归下降）分析方法。 首先，是文法的左递归性问题。一个文法是含有左递归的，如果存在非终结符P

含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即当试图用P去匹配输入串时，我们会发现，在没有识别任何输入符号的情况下，又得重新要求P去进行新的匹配。

其次，由于回溯就碰到一大堆麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经做的一大堆语义工作推倒重来。

第三，在上述的自上而下分析过程中，当一个非终结符用某一个候选匹配成功时，这种成功可能仅是暂时的。

第四，当最终报告分析不成功时，我们难于知道输入串中出错的确切位置。

最后，由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此效率很低，代价极高。

一、 理解确定的自顶向下分析思想

确定的自顶向下分析方法，是从某文法的开始符号出发，考虑如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或如何构造一棵相应的语法树，其末端结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号串为该文法的句子。

二、 掌握LL（1）文法的判别步骤

一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法。

某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。

掌握LL(1)文法的定义。熟练掌握FIRST集、FOLLOW集和SELECT集的计算方法。

三、某些非LL（1）文法到LL（1）文法的等价交换

理解两种非LL（1）文法的等价变换方法，特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL（1）文法的条件。

四、确定的自顶向下分析方法

掌握递归下降子程序的特点以及用PL/0程序分析PL/0编译程序的语法分析过程。

掌握如何构造预测分析表；

能用预测分析方法判断给定的输入符号串是否是该文法的句子。

你说的应该是编译原理吧。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 所以，当有左递归出现时，递归下降分析程序就会出现回朔，将可能产生无限的循环，所以递归下降分析的前提条件之一就是消除左递归。

Lex和Yacc应用方法(一)初识Lex

草木瓜 20070301

Lex(Lexical Analyzar 词法分析生成器)，Yacc(Yet Another Compiler Compiler

编译器代码生成器)是Unix下十分重要的词法分析，语法分析的工具。经常用于语言分

析，公式编译等广泛领域。遗憾的是网上中文资料介绍不是过于简单，就是跳跃太大，

入门参考意义并不大。本文通过循序渐进的例子，从0开始了解掌握Lex和Yacc的用法。

一Lex(Lexical Analyzar) 初步示例

先看简单的例子(注：本文所有实例皆在RetHat Linux下完成):

一个简单的Lex文件 exfirstl 内容：

%{

#include "stdioh"

%}

%%

[\n] ;

[0-9]+ printf("Int : %s\n",yytext);

[0-9]\[0-9]+ printf("Float : %s\n",yytext);

[a-zA-Z][a-zA-Z0-9] printf("Var : %s\n",yytext);

[\+\-\\/\%] printf("Op : %s\n",yytext);

printf("Unknown : %c\n",yytext[0]);

%%

在命令行下执行命令flex解析，会自动生成lexyyc文件：

[root@localhost liweitest]flex exfirstl

进行编译生成parser可执行程序：

[root@localhost liweitest]cc -o parser lexyyc -ll

[注意：如果不加-ll链结选项，cc编译时会出现以下错误，后面会进一步说明。]

/usr/lib/gcc-lib/i386-redhat-linux/322////crt1o(text+0x18): In function `_start':

/sysdeps/i386/elf/startS:77: undefined reference to `main'

/tmp/cciACkbXo(text+0x37b): In function `yylex':

: undefined reference to `yywrap'

/tmp/cciACkbXo(text+0xabd): In function `input':

: undefined reference to `yywrap'

collect2: ld returned 1 exit status

创建待解析的文件 filetxt：

title

i=1+39;

a3=909/6

bcd=4%9-333

通过已生成的可执行程序，进行文件解析。

[root@localhost liweitest]# /parser < filetxt

Var : title

Var : i

Unknown : =

Int : 1

Op : +

Float : 39

Unknown : ;

Var : a3

Unknown : =

Int : 909

Op : /

Int : 6

Var : bcd

Unknown : =

Int : 4

Op : %

Int : 9

Op : -

Int : 333

到此Lex用法会有个直观的了解：

1定义Lex描述文件

2通过lex，flex工具解析成lexyyc文件

3使用cc编译lexyyc生成可执行程序

再来看一个比较完整的Lex描述文件 exsecl ：

%{

#include "stdioh"

int linenum;

%}

%%

title showtitle();

[\n] linenum++;

[0-9]+ printf("Int : %s\n",yytext);

[0-9]\[0-9]+ printf("Float : %s\n",yytext);

[a-zA-Z][a-zA-Z0-9] printf("Var : %s\n",yytext);

[\+\-\\/\%] printf("Op : %s\n",yytext);

printf("Unknown : %c\n",yytext[0]);

%%

showtitle()

{

printf("----- Lex Example -----\n");

}

int main()

{

linenum=0;

yylex(); / 进行分析 /

printf("\nLine Count: %d\n",linenum);

return 0;

}

int yywrap()

{

return 1;

}

进行解析编译：

[root@localhost liweitest]flex exsecl

[root@localhost liweitest]cc -o parser lexyyc

[root@localhost liweitest]/parser < filetxt

----- Lex Example -----

Var : i

Unknown : =

Int : 1

Op : +

Float : 39

Unknown : ;

Var : a3

Unknown : =

Int : 909

Op : /

Int : 6

Var : bcd

Unknown : =

Int : 4

Op : %

Int : 9

Op : -

Int : 333

Line Count: 4

这里就没有加-ll选项，但是可以编译通过。下面开始着重整理下Lex描述文件l。

二Lex(Lexical Analyzar) 描述文件的结构介绍

Lex工具是一种词法分析程序生成器，它可以根据词法规则说明书的要求来生成单词识

别程序，由该程序识别出输入文本中的各个单词。一般可以分为<定义部分><规则部

分><用户子程序部分>。其中规则部分是必须的，定义和用户子程序部分是任选的。

(1)定义部分

定义部分起始于 %{ 符号，终止于 %} 符号，其间可以是包括include语句、声明语句

在内的C语句。这部分跟普通C程序开头没什么区别。

%{

#include "stdioh"

int linenum;

%}

(2) 规则部分

规则部分起始于"%%"符号，终止于"%%"符号，其间则是词法规则。词法规则由模式和

动作两部分组成。模式部分可以由任意的正则表达式组成，动作部分是由C语言语句组

成，这些语句用来对所匹配的模式进行相应处理。需要注意的是，lex将识别出来的单

词存放在yytext[]字符数据中，因此该数组的内容就代表了所识别出来的单词的内容。

类似yytext这些预定义的变量函数会随着后面内容展开一一介绍。动作部分如果有多

行执行语句，也可以用{}括起来。

%%

title showtitle();

[\n] linenum++;

[0-9]+ printf("Int : %s\n",yytext);

[0-9]\[0-9]+ printf("Float : %s\n",yytext);

[a-zA-Z][a-zA-Z0-9] printf("Var : %s\n",yytext);

[\+\-\\/\%] printf("Op : %s\n",yytext);

printf("Unknown : %c\n",yytext[0]);

%%

A规则部分的正则表达式

规则部分是Lex描述文件中最为复杂的一部分，下面列出一些模式部分的正则表达式字

符含义：

A-Z, 0-9, a-z 构成模式部分的字符和数字。

- 指定范围。例如：a-z 指从 a 到 z 之间的所有字符。

\ 转义元字符。用来覆盖字符在此表达式中定义的特殊意义，

只取字符的本身。

[] 表示一个字符集合。匹配括号内的任意字符。如果第一个字

符是^那么它表示否定模式。例如: [abC] 匹配 a, b, 和C

的任何一个。

^ 表示否定。

匹配0个或者多个上述模式。

+ 匹配1个或者多个上述模式。

匹配0个或1个上述模式。

$ 作为模式的最后一个字符时匹配一行的结尾。

{ } 表示一个模式可能出现的次数。 例如: A{1,3} 表示 A 可

能出现1次或3次。[a-z]{5} 表示长度为5的，由a-z组成的

字符。此外，还可以表示预定义的变量。

匹配任意字符，除了 \n。

( ) 将一系列常规表达式分组。如：{Letter}({Letter}|{Digit})

| 表达式间的逻辑或。

"一些符号" 字符的字面含义。元字符具有。如："" 相当于 [\]。

/ 向前匹配。如果在匹配的模式中的"/"后跟有后续表达式，

只匹配模版中"/"前面的部分。如：模式为 ABC/D 输入 ABCD，

时ABC会匹配ABC/D，而D会匹配相应的模式。输入ABCE的话，

ABCE就不会去匹配ABC/D。

B规则部分的优先级

规则部分具有优先级的概念，先举个简单的例子：

%{

#include "stdioh"

%}

%%

[\n] ;

A {printf("ONE\n");};

AA {printf("TWO\n");};

AAAA {printf("THREE\n");};

%%

此时，如果输入内容：

[root@localhost liweitest]# cat file1txt

AAAAAAA

[root@localhost liweitest]# /parser < file1txt

THREE

TWO

ONE

Lex分析词法时，是逐个字符进行读取，自上而下进行规则匹配的，读取到第一个A字符

时，遍历后发现三个规则皆匹配成功，Lex会继续分析下去，读至第五个字符时，发现

"AAAA"只有一个规则可用，即按行为进行处理，以此类推。可见Lex会选择最长的字符

匹配规则。

如果将规则

AAAA {printf("THREE\n");};

改为

AAAAA {printf("THREE\n");};

/parser < file1txt 输出结果为：

THREE

TWO

再来一个特殊的例子：

%%

title showtitle();

[a-zA-Z][a-zA-Z0-9] printf("Var : %s\n",yytext);

%%

并输入title，Lex解析完后发现，仍然存在两个规则，这时Lex只会选择第一个规则，下面

的则被忽略的。这里就体现了Lex的顺序优先级。把这个例子稍微改一下：

%%

[a-zA-Z][a-zA-Z0-9] printf("Var : %s\n",yytext);

title showtitle();

%%

Lex编译时会提示：warning, rule cannot be matched这时处理title字符时，匹配

到第一个规则后，第二个规则就无效了。

再把刚才第一个例子修改下，加深下印象！

%{

#include "stdioh"

%}

%%

[\n] ;

A {printf("ONE\n");};

AA {printf("TWO\n");};

AAAA {printf("THREE\n");};

AAAA {printf("Cannot be executed!");};

/parser < file1txt 显示效果是一样的，最后一项规则肯定是会忽略掉的。

C规则部分的使用变量

且看下面示例：

%{

#include "stdioh"

int linenum;

%}

int [0-9]+

float [0-9]\[0-9]+

%%

{int} printf("Int : %s\n",yytext);

{float} printf("Float : %s\n",yytext);

printf("Unknown : %c\n",yytext[0]);

%%

在%}和%%之间，加入了一些类似变量的东西，注意是没有;的，这表示int，float分

别代指特定的含义，在两个%%之间，可以通过{int}{float}进行直接引用，简化模

式定义。

(3) 用户子程序部分

最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子

程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，

当编译时不带-ll选项时，是必须加入main函数和yywrap(yywrap将下后面说明)。如：

%%

showtitle()

{

printf("----- Lex Example -----\n");

}

int main()

{

linenum=0;

yylex(); / 进行Lex分析 /

printf("\nLine Count: %d\n",linenum);

return 0;

}

int yywrap()

{

return 1;

}

三Lex(Lexical Analyzar) 一些的内部变量和函数

内部预定义变量：

yytext char 当前匹配的字符串

yyleng int 当前匹配的字符串长度

yyin FILE lex当前的解析文件，默认为标准输出

yyout FILE lex解析后的输出文件，默认为标准输入

yylineno int 当前的行数信息

内部预定义宏：

ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的

默认动作

内部预定义的函数：

int yylex(void) 调用Lex进行词法分析

int yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1，就停止解

析。 因此它可以用来解析多个文件。代码可以写在第三段，这

样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的

文件，直到所有的文件都被解析。最后，yywrap() 可以返回1

来表示解析的结束。

lex和flex都是解析Lex文件的工具，用法相近，flex意为fast lexical analyzer generator。

可以看成lex的升级版本。

相关更多内容就需要参考flex的man手册了，十分详尽。

四关于Lex的一些综述

Lex其实就是词法分析器，通过配置文件l，依据正则表达式逐字符去顺序解析文件，

并动态更新内存的数据解析状态。不过Lex只有状态和状态转换能力。因为它没有堆栈，

它不适合用于剖析外壳结构。而yacc增加了一个堆栈，并且能够轻易处理像括号这样的

结构。Lex善长于模式匹配，如果有更多的运算要求就需要yacc了。

目录

第1章　编译器概述

　11　为什么要学习编译技术

　12　编译器和解释器

　13　编译器的功能分解和组织结构

　14　编译器的伙伴

　15　编译器的复杂性

　16　编译器的设计与实现

　17　编译器的测试与维护

第2章　一个微型编译器

　21　基础知识

　22　ToyL语言

　23　ToyL语言词法分析器

　24　ToyL语言语法分析器

　25　ToyL语言解释器

　26　ToyL语言编译器

第3章　有穷自动机与词法分析

　31　词法分析基础

311　词法分析器的功能

312　单词识别

313　词法分析的复杂性

314　字符串

315　保留字处理

316　空格符、回车符、换行符

317　括号类配对预检

318　词法错误修正

319　词法分析独立化的意义

　32　有穷自动机

321　确定有穷自动机的定义

322　确定有穷自动机的实现

323　非确定有穷自动机

324　NFA到DFA的转换

325　确定有穷自动机的极小化

326　自动机状态转换表的实现

　33　正则表达式

331　正则符号串集

332　正则表达式的定义

333　正则表达式的局限性

334　正则定义

335　正则表达式到有穷自动机的转换

　34　词法分析器的构造

341　用DFA人工构造词法分析器

342　词法分析器的生成器Lex

　练习

第4章　文法与语法分析

　41　语法分析

411　语法分析器的输入

412　语法分析的任务

413　语法分析方法分类

　42　文法和文法分析

421　上下文无关文法和语言

422　最左推导和最右推导

423　语法分析树与二义性

424　文法分析算法

425　自顶向下方法概述

426　自底向上方法概述

　43　递归下降法——自顶向下分析

431　递归下降法原理

432　消除公共前缀

433　代入

434　消除左递归

　44　LL分析方法——自顶向下分析

441　LL(1)文法

442　LL(1)分析表

443　LL(1)分析的驱动器

444　LL(1)中的If-Then-Else问题

445　LL(1)分析器的自动生成器LLGen

446　LL(1)分析法与递归下降法的比较

447　正则文法

　45　LR方法——自底向上分析

451　句柄

452　活前缀

453　归约活前缀识别器——LR(0)自动机

454　LR(0)文法及其分析算法

455　SLR(1)文法及其分析算法

456　LR(1)文法

457　LALR(1)文法

458　二义性文法的处理

459　另一种Shift-Reduce分析技术：简单优先法

4510　LL(1)和LALR(1)方法比较

　46　LR分析器的生成器

461　LALR分析器的生成器YACC

462　LALR分析器的生成器LALRGen

　47　语法错误处理

471　错误恢复和修复

472　递归下降分析的错误恢复

473　LL分析的错误恢复

474　LR分析的错误恢复

　练习

第5章　语义分析

　51　语义分析基础

511　语义分析内容

512　标识符信息的内部表示

513　类型信息的内部表示

514　运行时值的表示

　52　符号表

521　符号表查找技术

522　符号表的局部化

523　二叉式局部符号表

524　散列式全局符号表

525　嵌套式全局符号表

526　符号表界面函数

　53　类型分析

531　类型的等价性和相容性

532　类型分析的总控算法

533　类型名分析

534　枚举类型分析

535　数组类型分析

536　记录类型分析

537　联合类型分析

538　指针类型分析

539　递归类型分析

　54　声明的语义分析

541　声明的语法结构

542　标号声明部分的语义分析

543　常量声明部分的语义分析

544　类型声明部分的语义分析

545　变量声明部分的语义分析

546　过程、函数声明的语义分析

　55　执行体的语义分析

551　执行体的语义分析

552　带标号语句和转向语句的语义分析

553　赋值语句的语义分析

554　条件语句的语义分析

555　while循环语句的语义分析

556　for循环语句的语义分析

557　过程调用语句的语义分析

558　表达式的语义分析

559　变量的语义分析

　练习

第6章　运行时的存储环境

　61　运行时的存储空间结构与分配

611　运行时的存储空间基本结构

612　静态区的存储分配

613　栈区的存储分配

614　堆区的存储分配

615　堆区空间管理

　62　过程活动记录与栈区组织结构

621　过程活动记录

622　活动记录的填写

623　栈区组织结构——AR链

　63　运行时的变量访问环境

631　可访问活动记录

632　局部Display表方法

633　静态链方法

634　全局Display表方法和寄存器方法

635　无嵌套时的AR及访问环境

　64　分程序和动态数组空间

641　无动态数组时的分程序空间

642　动态数组空间

　练习

第7章　面向语法的语义描述

　71　动作文法

711　动作文法定义

712　动作文法的递归实现

713　动作文法的LL实现

714　动作文法的LR实现

　72　动作文法应用

721　用动作文法描述表达式计算

722　用动作文法描述表达式抽象树的构造

723　用动作文法描述语句抽象树的构造

　73　抽象动作文法及其应用

731　抽象变量

732　抽象动作文法

733　栈式LL动作文法驱动器

734　抽象动作文法到栈式LL动作文法的转换

735　栈式LR动作文法驱动器

736　抽象动作文法到栈式LR动作文法的转换

　74　属性文法

741　属性文法定义

742　属性语法树和属性依赖图

743　计算顺序

744　属性值的计算方法

745　拷贝型属性文法

　75　属性文法在编译器设计中的应用

751　类型树的属性文法描述

752　表达式中间代码的属性文法描述

753　变量中间代码的属性文法描述

754　语句中间代码的属性文法描述

755　正则表达式到自动机转换的属性文法描述

　76　S-属性文法及其属性计算

761　S-属性文法

762　S-属性文法的递归实现

763　S-属性文法的LR实现

　77　L-属性文法及其属性计算

771　L-属性文法

772　L-属性文法的递归实现

773　L-属性文法的LR(1)实现

　78　语义分析器的自动生成系统

781　YACC

782　LALRGen

783　Accent系统

　练习

第8章　中间代码生成

　81　中间代码

811　中间代码的种类

812　后缀式中间代码

813　三地址中间代码

814　抽象语法树和无环有向图

815　多元式中间代码

816　中间代码分量ARG结构

　82　表达式的中间代码生成

821　表达式的语义信息

822　表达式的中间代码

823　变量的中间代码

824　表达式的中间代码生成

825　变量的中间代码生成

826　布尔表达式的短路中间代码

　83　原子语句的中间代码生成

831　输入/输出语句的中间代码生成

832　goto语句和标号定位语句的中间代码生成

833　return语句的中间代码生成

834　赋值语句的中间代码生成

835　函数（过程）调用的中间代码生成

　84　结构语句的中间代码生成

841　条件语句的中间代码生成

842　while语句的中间代码生成

843　repeat语句的中间代码生成

844　for语句的中间代码生成

845　case语句的中间代码生成

846　函数声明的中间代码生成

　练习

第9章　中间代码优化

　91　引言

911　优化的目标和要求

912　优化的必要性

913　优化的内容

914　局部优化和全局优化

915　基本块和程序流图

　92　常表达式优化

921　常表达式的局部优化

922　基于常量定值分析的常表达式全局优化

923　常量定值分析

　93　公共表达式优化

931　基于相似性的公共表达式局部优化

932　基于值编码的公共表达式局部优化

933　基于活跃代码分析的公共表达式全局优化

934　活跃运算代码分析

　94　程序流图循环

941　循环的基本概念

942　支撑结点

943　自然循环

944　可归约程序流图

945　基于文本的循环及其处理

　95　循环不变代码外提

951　代码外提的基本概念

952　循环不变代码的判定

953　循环不变代码外提的条件

954　基于文本循环和定值表的不变代码外提

955　一种简单的外提优化方案

956　别名分析

957　过程与函数的副作用分析

　96　循环内归纳表达式的优化

961　归纳变量

962　归纳变量计算的优化算法原理

　练习

第10章　目标代码生成

　101　目标代码

1011　虚拟机代码

1012　目标机代码

1013　窥孔优化

　102　临时变量

1021　临时变量的特点

1022　临时变量的存储空间

1023　临时变量的存储分配

1024　变量状态描述

　103　寄存器

1031　寄存器分类及其使用准则

1032　寄存器分配单位

1033　寄存器状态描述

1034　寄存器分配算法

　104　基于三地址中间代码的目标代码生成

1041　目标地址生成

1042　间接目标地址的转换

1043　表达式中间代码的目标代码生成

1044　赋值中间代码的目标代码生成

1045　其他寄存器分配法

1046　标号和goto语句中间代码的目标代码生成

1047　return中间代码的目标代码生成

1048　变量中间代码的目标代码生成

1049　函数调用中间代码的目标代码生成

　105　基于AST的代码生成

1051　三地址中间代码到AST的转换

1052　标记需用寄存器个数

1053　从带寄存器个数标记的AST生成代码

　106　基于DAG的代码生成

1061　从AST到DAG的转换

1062　DAG排序和虚寄存器

1063　从带序号和虚寄存器标记的DAG生成代码

　107　代码生成器的自动生成

1071　代码生成器的自动化

1072　基于指令模板匹配的代码生成技术

1073　基于语法分析的代码生成技术

　练习

第11章　对象式语言的实现

　111　引言

　112　SOOL语法

1121　程序

1122　分程序

1123　类声明

1124　类型

1125　变量声明

1126　函数声明和方法声明

1127　语句

1128　变量

1129　表达式

11210　程序示例

　113　SOOL语义

1131　声明的作用域

1132　Class声明的语义

1133　语句的语义

　114　SOOL语义分析

1141　标识符的符号表项

1142　符号表结构

1143　符号表的局部化

　115　SOOL目标代码

1151　对象空间

1152　当前对象——self

1153　活动记录

1154　成员变量的目标地址

1155　表达式的目标代码

1156　Offset原理

1157　类的多态性

1158　目标代码区

1159　方法的动态绑定

11510　快速动态绑定目标代码

主要参考文献

以上就是关于用扩展的bnf表示法怎么消除文法左递归全部的内容，包括:用扩展的bnf表示法怎么消除文法左递归、自上而下分析法的详细解析、自顶向下的语法分析方法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！