编译原理word版

第三章复习：程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε复习：程序语言的语法描述∑*的子集U和V的连接（积）定义为UV＝{ αβ | α∈U & β∈V }V自身的 n次积记为V n=VV (V)规定V0={ε}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记 V＋＝VV*，称V+是V的正规闭包。

复习：程序语言的语法描述上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT ，VN，S，P)，其中VT：终结符集合(非空)V N ：非终结符集合(非空)，且VT⋂VN=∅S：文法的开始符号，S∈VNP：产生式集合(有限)，每个产生式形式为P→α， P∈VN ，α∈ (VT⋃VN)*开始符S至少必须在某个产生式的左部出现一次。

复习：程序语言的语法描述定义：称αAβ直接推出αγβ，即αAβ⇒αγβ仅当A →γ是一个产生式，且α，β∈ (VT ⋃VN)*。

如果α1⇒α2⇒⋯⇒αn，则我们称这个序列是从α1到αn的一个推导。

若存在一个从α1到αn的推导，则称α1可以推导出αn。

复习：程序语言的语法描述最左推导：任何一步α⇒β都是对α中的最左非终结符进行替换。

最右推导：任何一步α⇒β都是对α中的最右非终结符进行替换。

复习：程序语言的语法描述用一张图表示一个句型的推导,称为语法树。

复习：程序语言的语法描述定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。

语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。

复习：程序语言的语法描述形式语言鸟瞰♦0型(短语文法，图灵机)：产生式形如：α→β其中：α∈ (VT ⋃VN)*且至少含有一个非终结符；β∈ (VT⋃VN)*♦1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|，仅 S→ε例外。

复习：程序语言的语法描述形式语言鸟瞰♦2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN ；β∈ (VT⋃VN)*。

♦3型(正规文法，有限自动机)：产生式形如： A →αB 或 A →α其中：α∈ VT *；A，B∈VN产生式形如： A → Bα或 A →α其中：α∈ VT *；A，B∈VN第三章词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。

词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序3.1 对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如 begin，repeat，⋯标识符——表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，⋯界符：逗号、分号、括号和空白输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。

若一个种别只有一个单词符号，则种别编码就代表该单词符号。

假定基本字、运算符和界符都是一符一种。

若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。

标识符单列一种；常数按类型分种(整、实、布尔等）。

例 C程序while (i>=j) i--;输出单词符号：< while, - >< (, - >< id, 指向i的符号表项的指针 >< >=, - >< id, 指向j的符号表项的指针 >< ), - >< id, 指向i的符号表项的指针 >< --, - >< ;, - >二、词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。

不作为一遍：将其处理为一个子程序。

词法分析器的结构输入串放在输入缓冲区中。

预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区二、单词符号的识别:超前搜索1 基本字识别:例如:DO99K=1，10 DO 99 K = 1，10IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字2 标识符识别:字母开头的字母数字串，后跟界符或算符3 常数识别:识别出算术常数并将其转变为二进制内码表示。

有些也要超前搜索。

5.EQ.M5.E084 算符和界符的识别把多个字符符合而成的算符和界符拼合成一个单一单词符号。

:=， **， .EQ. ， ++，--，>=三、状态转换图1 概念状态转换图是一张有限方向图。

一个状态转换图可用于识别(或接受)一定的字符串。

6)IsLetter和 IsDisgital 布尔函数，判断ch中字符是否为字母和数字7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字则给出它的编码，否则回送08) Retract 子程序，把搜索指针回调一个字符位置9)InsertId 整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将strToken中的常数插入常数表，返回常数表指针。

int code, value;strToken := “ ”;/*置strToken为空串*/ GetChar(); GetBC();if (IsLetter())beginwhile (IsLetter() or IsDigit())beginConcat(); GetChar();endRetract();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit())beginwhile (IsDigit())beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =‘=’) return ($ASSIGN, -); else if (ch =‘+’) return ($PLUS, -);else if (ch =‘*’)beginGetChar();if (ch =‘*’) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =‘;’) return ($SEMICOLON, -); else if (ch =‘(’) return ($LPAR, -);else if (ch =‘)’) return ($RPAR, -);else ProcError( ); /* 错误处理*/3.3 正规表达式与有限自动机几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...} ∑*的子集U 和V 的连接（积）定义为 UV ＝{ αβ | α∈U & β∈V } V 自身的 n 次积记为 V n =VV…V 规定V 0={ε}，令V *=V 0∪V 1∪V 2∪V 3∪… 称V *是V 的闭包;记 V ＋＝VV * ，称V +是V 的正规闭包。

3.3.1 正规式和正规集正规集可以用正规表达式（简称正规式）表示。

正规表达式是表示正规集一种方法。

一个字集合是正规集当且仅当它能用正规式表示。

正规式和正规集的递归定义： 对给定的字母表∑1)ε 和∅都是∑上的正规式，它们所表示的正规集为{ε}和∅; 2) 任何a ∈∑ ，a 是∑上的正规式，它所表示的正规集为{a} ;3) 假定e 1和e 2都是∑上的正规式，它们所表示的正规集为L(e 1)和L(e 2)，则 i) (e 1|e 2)为正规式，它所表示的正规集为L(e 1)⋃L(e 2)， ii) (e 1.e 2)为正规式，它所表示的正规集为L(e 1)L(e 2)， iii) (e 1)*为正规式，它所表示的正规集为(L(e 1))*，仅由有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅由这些正规式表示的字集才是∑上的正规集。

所有词法结构一般都可以用正规式描述。

若两个正规式所表示的正规集相同，则称这两个正规式等价。

如 b(ab)*=(ba)*b (a *b *)*=(a|b)*对正规式，下列等价成立： e 1|e 2 = e 2|e 1 交换律e 1 |(e 2|e 3) = (e 1|e 2)|e 3 结合律 e 1(e 2e 3) = (e 1e 2)e 3 结合律 e 1(e 2|e 3) = e 1e 2|e 1e 3 分配律 (e 2|e 3)e 1 = e 2e 1|e 3 e 1 分配律 e ε = ε e = e e 1e 2 <> e 2 e 1 3.3.2 确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M 是一个五元式M=(S, ∑, f, S 0, F),其中： 1. S: 有穷状态集，2. ∑：输入字母表(有穷)，3. f: 状态转换函数，为S ⨯∑→S 的单值部分映射，f(s ，a)=s’表示：当现行状态为s ，输入字符为a 时，将状态转换到下一状态s’。

我们把s’称为s 的一个后继状态。

4. S∈S是唯一的一个初态；5 F⊆S ：终态集(可空)。

例如：DFA M=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定义如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3DFA可以表示为状态转换图。

假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用Σ上的不同的输入字符来作标记。

对于∑*中的任何字α，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于α，则称α为DFA M所识别(接收)DFA M所识别的字的全体记为L(M)。