编译原理 第三章 词法分析

编译原理 课件 配套 陈火旺 版

2.3 程序语言的语法描述 基本概念和术语：

字母表 ：由若干元素所组成的有限非空集合 Σ ,其中，每一元素称为符号，故有时又将

字母表称为符号集。 符号串(字) :Σ中的符号所组成的任何有限序 列。 符号串的长度:符号串中所含符号的个数. 例: |abc|=3。

编译原理 课件 配套 陈火旺 版

基本概念和术语 空符号串(空字):不包含任何符号的符号 串,记为ε(音：伊普西隆)。|ε|=0。 用Σ*表示Σ上的所有符号串的全体，空字也包括

在其中。 Σ*显然为一无限集

如：若Σ={a,b} 则Σ*={ ε,a,b,aa,ab,bb,ba,aaa,…} φ(音：弗爱):不含任何元素的空集{ } 注意：ε、{ }和{ε}的区别。

编译原理 课件 配套 陈火旺 版

基本概念和术语 符号串的运算：

符号串的连接：设x和y是两个符号串，将

符号串y直接拼接在x之后，此种操作为符 号串x和y的连接，记为xy。 例：若x=NPU,y=1108, 则xy=NPU1108。而yx=1108NPU εx=xε=x 符号串的方幂：符号串x与其自身的n-1次 连接称为此符号串的n次方幂，记作xn。特别：x0=ε

编译原理 课件 配套 陈火旺 版

基本概念和术语 符号串集合的运算：

设U,V为两个符号串的集合： 集合U,V的和记作U+V(或U∪V) 定义为： U+V={α|α∈U 或 α∈V} 集合U同V的积记作UV

定义为： UV={αβ | α ∈U 且 β ∈V } 一般UV≠VU,但(UV)W=U(VW).

编译原理 课件 配套 陈火旺 版

基本概念和术语例：设U = { a, b } V = { c, d } W= {df, ghi} 求UV=? UW=? UV={ ac, ad, bc, bd } UW={ adf, aghi, bdf, bghi }

编译原理 课件 配套 陈火旺 版

基本概念和术语 V自身的n次(连接)积记为：

Vn = V V…V (n个V) 规定V0= {ε}. 例：设A = { a, b }, 求A0 , A1, A2 A0 = {ε} A1 = { a, b} A2 = {aa, ab, ba, bb }

编译原理 课件 配套 陈火旺 版

基本概念和术语 V* = V0∪V1∪V2∪…,称V*是V的闭包。

闭包V*中的每个符号都是由V中的符号串 经有限次连接而成的。 记V+= VV*, 称V+是V的正则闭包设V= { a } 求V+ , V*

V* = {ε, a, aa, aaa, … } = { an | n>=0 } V+ = { a, aa, aaa, … } = { an | n>0 } 设U = { ac, b } 求U* U+ U* = {ε, ac, b, acac, acb, bac, bb, … } U+ = { ac, b, acac, acb, bac, bb, … }

编译原理 课件 配套 陈火旺 版

词法分析的任务：从左至右逐个字符地扫描源程序，产生 一个个的单词符号，把作为字符串的源程序 改造成为单词符号串的中间程序。

词法分析器/扫描器：执行词法分析的程序。

编译原理 课件 配套 陈火旺 版

词法分析器的功能如下图所示：由程序语言定义的具有固定意 义的标识符。也可称为保留字 或基本字。例如：Pascal中的 用来表示各种名字，如变量名、 begin,end,if等。 数组名、过程名等。它是不限的。 常数的类型一般有整型、实型、 布尔型、文字型等。它是不限 的。 运算符：如+、-、*、/ 等。 它是确定的。 界符：如逗号、分号、括号、 /*,*/ 等。它是确定的。

1、关键字

源 程 序

2、标识符

扫描器

3、常数

scanner

4、运算符5、界符

编译原理 课件 配套 陈火旺 版

词法分析器的功能：输入源程序，输出单词符号。 单词符号：一个程序语言的基本语法符号。分为以下5种。

确定

1、关键字：由程序语言定义的具有固定意义的标识符。也 可称为保留字或基本字。例如：Pascal中的begin, end,if等。它是确定的。 2、标识符：用来表示各种名字，如变量名、数组名、过程 名等。它是不限的。3、常数：常数的类型一般有整型、实型、布尔型、文字型 等。它是不限的。

不限

4、运算符：如+、-、*、/ 等。它是确定的。5、界符：如逗号、分号、括号、/*,*/ 等。它是确定的。

编译原理 课件 配套 陈火旺 版

单词符号的表示形式：词法分析器所输出的单词符号常常表示成二元式(单词种别，单词自身的值)。 单词种别可以用以下形式表示： 1、一类单词统一用一个整数值代表其属性。例如：1代表关键字， 2代表标识符等。 2、每一个单词一个类别。例如：1代表BEGIN,2代表END等。 单词自身的值可以表示成：常量的二进制表示；常量、变量等在符号表 种的地址码，等等。

注意：一个语言的单词符号如何分种，分几种，怎样编码，是一个技术问题。标识符一般同归为一种。常数则宜按类型(整、实、布尔)分。 关键字可以将其全体视为一种，也可一字一种。运算符可采用一符一种， 但也可把具有一定共性的视为一种。界符则一般采用一符一种。如何进 行分种主要取决于处理上的方便。 若是一符一种分种，单词自身值就不需要了。否则，要查符号表。

编译原理 课件 配套 陈火旺 版

例3-1:151-FORTRAN编译程序的词法分析器在扫描输入串 IF (5·EQ·M) GOTO 100逻辑IF 左括号 整常数 等号 标识符 右括号 GOTO 标号 (34,_)

后，它输出的单词符号串是：

IF为关键字，种别编码34, 采用一符一种的编码方式。 ‘(’为界符，种别编码2,采 (2,_) 用一符一种的编码方式。 常数类型，种别编码20,单词自 (20,‘5’的二进制表示) 身的值为‘5’的二进制表示。 等号为运算符，种别编码6, (6,_) 采用一符一种的编码方式。 M为标识符，种别编码26,单 (26,‘M’) 词自身值为‘M’。 ‘)’为界符，种别编码16, (16,_) 采用一符一种的编码方式。 GOTO为关键字，种别编码30, (30,_) 采用一符一种的编码方式。 100为标号，种别编码19,单词 (19,‘100’的二进制表示) 内部的值用100的二进制表示。

编译原理 课件 配套 陈火旺 版

例3-2 :下述C++代码段：while ( i >= j ) i - -; 经词法分析器处理以后，它将被转换为如下的单词符号串( while ,_ ) ( ( ,_ ) ( id ,指向i的符号表指针 ) ( >= ,_ )

( id ,指向j的符号表指针 )( ) ,_ ) ( id ,指向i的符号表指针 )

( - - ,_ )( ; ,_ )

编译原理 课件 配套 陈火旺 版

1、把词法分析从语法分析中脱

离出来的优点： 外存 使编译程序的结构更加简洁、清晰和条理化。 词法分析和语法分析方法不同，词法分析可以使用正则文法自动构造 单 源 scanner简单。 词程 符 语法 序 有利于提高语法分析的效率。 号

分析 可以改善词法分析的细节，甚至于一个语法分析配几个scanner,把不同 的输入变成一种内部表示。 2、把词法分析作为独立的一遍 scanner 语法分析 scanner作为子程序 scanner当作一遍。 把scanner当作子程序。

scanner

源程序

scanner作为一遍

编译原理 课件 配套 陈火旺 版

设计前提：

输入

列表 把scanner作为一个独立的子程序； 输入缓冲区 预处理 词法分析器的任务为输出单词符号。 子程序

扫描缓冲区

预 处 理 部 分

必要性：编辑性字符如空白符、回车符等，除了出现在文字和 扫描器 常数中以外，在别处出现都没有意义。 扫 单词符号 描 功 能： 剔除无用字符。 器 语法分析器 实 现： 预处理子程序。 图2.1 词法分析器

编译原理 课件 配套 陈火旺 版

若识别输入语句 IF (5.EQ.M …… 此处隐藏：2102字，全部文档内容请下载后查看。喜欢就下载吧 ……