第18讲 项目集规范簇的构造-讲义-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

第4讲 词法分析概述

0．本节教学内容：

1）回顾上一章的内容，为本章打下基础

2）教材第3章 3.1

3）教材第3章 3.2

一．本节教学要求：

掌握词法分析器的任务和功能，理解词法分析器的设计,为实验部分词法分

析器的手工生成打下基础。

二．教学方式及学时分配：

采用教师讲授+学生提问的方式

总共2学时，主要分配在第3.2节上，提问及总结以前的内容大约20分钟

三．教学重点:

 词法分析器的任务和功能

 词法分析器的设计

 状态转换图

四．教学难点：

 词法分析器的设计

 状态转换图

五．教学过程中的注意事项：

1．首先介绍词法分析的功能、输入、输出接口，让学生对语法分析的地位

和如何编写有一个整体的把握，这样学生做实验才容易上手。

2．以讲解+课堂练习的方式，巩固学生对具体实现方法和步骤的练习。

六．学习方法：

1．从整体上把握词法分析器与周围各部分的关系，为理解和实验作准备。

2．从本节起实验开始，具有一定的难度，要调整学习方法，课上认真理解，

课下多动手实践。

七．教学内容

1．复习

2．词法分析器的功能

词法分析的主要任务是从左至右逐个字符地对源程序进行扫描，将字符拼接

成单词，每当识别出一个单词，就产生其种别码，把作为字符串的源程序改造成

单词符号串的中间形式，提交给语法分析程序使用。

它是编译器中唯一与源程序打交道的部分，主要工作有：

（1）按规则识别单词，输出单词本身及其种别码。这是词法分析的主要任

务；

（2）滤掉源程序中的无用成分，如注释、空格、回车换行等。这些部分只

是有助于源程序的阅读，对生成代码无用；

（3）调用出错处理器，识别并定位错误。词法错误是源程序中的常见错误，

如出现非法字符、违反构词规则的单词等；

（4）调用符号管理器，将识别出来的单词及其属性进行管理。

有些源语言支持宏预处理功能，也可以在词法分析程序中完成。

3．单词的类型

程序设计语言可以根据单词在语言中的作用将单词大致分为5类：

第三章 习题解答

6．每个表达式的推导及语法树分别如下：

(1)

=>

=>

=> i

(2)

=>

=>

=>()

=>()

=>()

=>(i)

(3)

=>

=>*

=>*

=>i*

=>i*i

(4)

=> +

=> +

=> *+

=> *+

=> i*+

=> i*i+

=> i*i+

=> i*i+i

(5)

=> +

=> +

=> +

=> i+

=> i+

=>i+

=>i+(+)

=> i+(+) => i+(+)

=> i+(i+)

=> i+(i+)

=>i+(i+i)

(6)

=> +

=> +

=> +

=> i+

=> i+*

=> i+*

=> i+i*

=> i+i*i

i()i*ii图（1）图（2）图（3） ()+*iii+i+ii图（4）图（5）

+i图（6）*ii

11．根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：

E => E+T => E+T*F ，所以E+T*F是该文法的一个句型。由右图的语法树也可以看出，E+T*F是该文法的一个句型。

这个句型的所有短语为：E+T*F, T*F

直接短语为：T*F

句柄为：T*F

13． EE + TT * F(1)最左推导：S=>ABS

=>a1BS

=> a1SBBS

=> a1BBS

=> a1b1BS

=> a1b1b2S

=> a1b1b2Aa3

=> a1b1b2a2a3

最右推导：S=>ABS

=> ABAa3

=> ABa2a3

=> ASBBa2a3

=> ASBb2a2a3

=> ASb1b2a2a3

=> Ab1b2a2a3

=> a1b1b2a2a3

(2)该文法产生式集合P可能有如下规则：S→ABS|Aa|ε

第２８卷第６期　２０１０年１１月　佳木斯大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉａｍｕｓｉ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．２８　Ｎｏ．６　Ｎｏｖ．　２０ｌ０　

文章编号：１００８—１４ｏ２（２ＯｌＯｊＯ６—０８８８—０３　

编译原理中项目集规范族的分析与研究①　

岳小婷　

（东北财经大学管理科学与工程学院．辽宁大连１　１６０２５）　

摘要：　ＬＲ分析法是一种应用较广泛的语法分析方法，项目集规范族是构造ＬＲ分析表的基　

础．本文将词法分析方法与语法分析方法联系起来，以有限自动机知识为基础，给出了一种基于　

自动机的构造项目集规范族的方法，然后，给出了一种更简洁的方法，并比较了两种方法的异同．　关键词：　编译程序；ＬＲ分析法；项目集规范族　

中图分类号：ＴＰ３１４　文献标识码：Ａ　

０　引　言　１．１构造一个识别文法所有活前缀的ＮＦＡ　

编译程序包括词法分析、语法分析、语义分析、　

中间代码生成、代码优化、代码生成等阶段．其中，　

词法分析阶段以高级语言编写的源程序作为输入，　

利用确定有限自动机ＤＦＡ识别单词，输出由记号　

名和属性值构成的二元式序列…；语法分析以二　

元式序列中的记号名序列作为输人，将其视为句　

子，判断它是否能由源语言的文法产生．语法分析　

的方法有自上而下和自下而上两种方法，ＬＲ分析　

法是一种自下而上方法，因此在每一步规约时都需　

要找到当前右句型的旬柄．句柄是符号串，因而可　

以按照词法分析的方法，构造一个有限自动机　

ＤＦＡ，将句柄的识别划分为若干状态，每个状态识　

别一个字符，经过若干状态就可以识别出右句型的　

活前缀，同时也识别出句柄的左部的部分字符．因　

而，对旬柄的识别就转变成对活前缀的识别．识别　

活前缀的ＤＦＡ中的所有状态的集合就是项目集规　

范族．　

１　利用ＤＦＡ构造项目集规范族　

词法分析中，在构造识别单词的确定有限自动　

机ＤＦＡ时，一般是先构造一个非确定有限自动机　

第二章

P36-6

(1)

LG()1是0~9组成的数字串

(2)

最左推导:

NNDNDDNDDDDDDDDDDDDDNNDDDDNNDNDDDDDDDD0010120127334556568

最右推导:

NNDNNDNNDNDNNDNDNNDNNDND77272712712701274434886868568

P36-7

G(S)

ONODNSOAOAADN1357924680|||||||||||

P36-8

文法：

ETETETTFTFTFFEi|||*|/()|

最左推导:

EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()

最右推导:

EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()

语法树：/******************************** EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i

*****************/

P36-9

句子iiiei有两个语法树：

SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiiei

P36-10

/**************

) (|)(|STTTSS

***************/

P36-11

/***************

L1:

||cCCabaAbAACS