《编译原理》课程教学资源：第二章 语言描述与实现 Language Description and Implementation 2.1 程序语言的语法描述

Part 2 Language Description and Implementation 语言描述与实现

Part 2 Language Description and Implementation 语言描述与实现

程序语言的定义 ■程序语言由两方面定义: 语法 口语义 口语用

程序语言的定义 ◼ 程序语言由两方面定义： 语法 语义 语用

教学要点 ■上下文无关文法 ■直接推出与推导、最左推导与最右推导 ■句型、句子与语言 ■递归与语言 ■语法树与二义性 ■EBNF与语法图 ■乔姆斯基文法

教学要点 ◼ 上下文无关文法 ◼ 直接推出与推导、最左推导与最右推导 ◼ 句型、句子与语言 ◼ 递归与语言 ◼ 语法树与二义性 ◼ EBNF与语法图 ◼ 乔姆斯基文法

语法 ■程序本质上是一定字符集上的字符串。 语法:一组规则,用它可以形成和产生 个合式(wel1 formed的程序

一 . 语法 ◼ 程序本质上是一定字符集上的字符串。 ◼ 语法：一组规则，用它可以形成和产生一 个合式(well-formed)的程序

语法 ■词法规则:单词符号的形成规则 口单词符号是语言中具有独立意义的最基 本结构。一般包括:常数、标识符、基 本字、算符、界符等。 □描述工具:有限自动机 语法规则:语法单位的形成规则。 口语法单位通常包括:表达式、语句、分 程序、过程、函数、程序等; □描述工具:上下文无关文法

语 法 ◼ 词法规则：单词符号的形成规则。 单词符号是语言中具有独立意义的最基 本结构。一般包括：常数、标识符、基 本字、算符、界符等。 描述工具：有限自动机 ◼ 语法规则：语法单位的形成规则。 语法单位通常包括：表达式、语句、分 程序、过程、函数、程序等; 描述工具：上下文无关文法

■G1 E→i E→E+E E→E米E E→(E) ■语法规则和词法规则定义了程序的的形 式结构。定义语法单位的意义属于语义 问题

◼ G1: E→i E→E+E E→E*E E→(E) ◼ 语法规则和词法规则定义了程序的的形 式结构。定义语法单位的意义属于语义 问题

二.语义 ■语义:一组规则,用它可以定义一个程 序的意义 ■描述方法 □自然语言描述:隐藏错误、二义性和不完整 口形式描述: 操作语义 指称语义 代数语义

二. 语义 ◼ 语义：一组规则，用它可以定义一个程 序的意义。 ◼ 描述方法： 自然语言描述：隐藏错误、二义性和不完整 性 形式描述：  操作语义  指称语义  代数语义

21程序语言的语法描述 ■几个概念: 口考虑一个有穷字母表∑字符集 口其中每一个元素称为一个字符 口∑上的字(也叫字符串)是指由∑中的字符所构 成的一个有穷序列 口不包含任何字符的序列称为空字,记为e 口用∑*表示∑上的所有字的全体,包含空字e 例如:设∑={a,b},则 ∑*={ε,a,b,aa,ab,ba,bb,a

2.1 程序语言的语法描述 ◼ 几个概念: 考虑一个有穷 字母表∑ 字符集 其中每一个元素称为一个字符 ∑上的字(也叫字符串) 是指由∑中的字符所构 成的一个有穷序列 不包含任何字符的序列称为空字，记为ε 用∑*表示∑上的所有字的全体,包含空字ε 例如: 设 ∑={a， b}，则 ∑*={ε,a,b,aa,ab,ba,bb,aaa,...}

∑的子集U和V的连接(积)定义为 UV=t U& V自身的n次积记为 Vn=W.v ■规定v°={},令 V=VOUV1UV2UV3U 称V是V的闭包; ■记V+=VV,称V是V的正规闭包

◼ ∑*的子集U和V的连接（积）定义为 UV＝{ | U & V } V自身的 n次积记为 Vn=VV…V ◼ 规定V0={ }，令 V*=V0∪V1∪V2∪V3∪… 称V*是V的闭包; ◼ 记 V＋＝VV* ，称V+是V的正规闭包

21.1上下文无关文法 上下文无关文法( Context-free grammer,CFG)是这样一种文法,它所定义的 语法范畴(或语法单位)是完全独立于这种范 畴可能出现的环境的

上下文无关文法（Context-free grammer,CFG)是这样一种文法，它所定义的 语法范畴（或语法单位）是完全独立于这种范 畴可能出现的环境的。 2.1.1 上下文无关文法