第二章 程序语言的语法描述概要课件

高级语言及其语法描述西北大学软件工程研究所龚晓庆高级语言及其语法描述西北大学软件工程研究所龚晓庆2022/11/12SEI2Contents程序语言的定义1高级语言的一般特性2上下文无关文法3形式语言42022/11/11SEI2Contents程序语言的定义12022/11/12SEI32.1程序语言的定义一个程序语言是一个记号系统如同自然语言一样，程序主要由语法和语义两个方面定义语法描述程序中单词的排列方式或结构语义描述程序的含义有时候语言定义也包含语用信息语用主要是有关程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学或计算机的对象和操作）联系起来2022/11/11SEI32.1程序语言的定义一个程序语2022/11/12SEI4语法任何语言程序都可以看作是一定字符集（字母表）上的字符串合式的程序形式上正确的程序所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序这些规则的一部分称为词法规则另一部分称为语法规则（产生规则）词法规则和语法规则规定了程序的形式结构，是判断输入字符串是否构成一个合式程序的依据。2022/11/11SEI4语法任何语言程序都可以看作是一定2022/11/12SEI5词法规则单词符号单词符号是语言中具有独立意义的最基本结构常数、标识符、基本字、算符、界符词法规则是指单词符号的形成规则描述和分析的工具有限自动机（FiniteAutomata）正规表达式正规文法2022/11/11SEI5词法规则单词符号2022/11/12SEI6语法规则语法范畴（语法单位）表达式、语句、过程、程序语法规则是语法单位的形成规则，它规定了如何从单词符号形成更大的结构，即语法单位。描述工具上下文无关文法（Context-FreeGrammar，CFG）2022/11/11SEI6语法规则语法范畴（语法单位）2022/11/12SEI7语义所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则语义规则的描述没有公认的形式系统现常用属性文法2022/11/11SEI7语义所谓一个语言的语义是指这样的2022/11/12SEI8程序语言和程序程序语言的基本功能描述数据和对数据的运算程序所谓一个程序，从本质上说是描述一定数据的处理过程2022/11/11SEI8程序语言和程序程序语言的基本功能2022/11/12SEI9程序的层次结构程序子程序或分程序语句数据引用表达式算符函数调用2022/11/11SEI9程序的层次结构程序子程序或分程序2022/11/12SEI102.2高级语言的一般特性高级语言的分类1程序结构2数据类型和数据结构3语句与控制结构42022/11/11SEI102.2高级语言的一般特性高级2022/11/12SEI11高级语言的分类强制式语言命令驱动，面向语句应用式语言函数式语言，LISP基于规则的语言检查条件，执行动作，Prolog面向对象语言封装，继承，多态2022/11/11SEI11高级语言的分类强制式语言2022/11/12SEI12程序结构示例过程式程序FORTRANPascal基于对象/面向对象程序AdaJava2022/11/11SEI12程序结构示例过程式程序2022/11/12SEI13数据类型与操作数据类型的三要素用于区别这种类型数据的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作数据类型初等数据类型数据结构抽象数据类型2022/11/11SEI13数据类型与操作数据类型的三要素2022/11/12SEI14初等数据类型数值数据整数，实数；可以进行算术运算逻辑数据逻辑型数据，位串；字符数据字符和字符串指针类型2022/11/11SEI14初等数据类型数值数据2022/11/12SEI15标识符和名字标识符程序中的各种名字都用标识符表示标识符的构成规则名字具有明确的意义和属性存储单元、值类型、作用域2022/11/11SEI15标识符和名字标识符2022/11/12SEI16数据结构数组下标、下标变量数组的存放方式与元素地址记录字段，域存放方式与边界对齐其它字符串、表、栈2022/11/11SEI16数据结构数组2022/11/12SEI17抽象数据类型抽象数据类型包括数据对象的一个集合作用于这些数据对象的抽象运算的集合这种类型对象的封装2022/11/11SEI17抽象数据类型抽象数据类型包括2022/11/12SEI18语句与控制结构表达式变量、常数是表达式；若E1、E2为表达式，θ是一个二元算符，则E1θE2是表达式；若E是表达式，θ是一元算符，则θE（或Eθ）是表达式；若E是表达式，则（E）是表达式。算符操作数个数、优先级、结合性2022/11/11SEI18语句与控制结构表达式例——C语言运算符例——C语言运算符2022/11/12SEI20语句按功能分类说明性语句执行性语句赋值、控制、输入输出按形式分类简单语句复合语句2022/11/11SEI20语句按功能分类2022/11/12SEI212.3程序语言的语法描述上下文无关文法1文法和语言2推导、语法分析树3二义文法42022/11/11SEI212.3程序语言的语法描述上下语法语言的语法是程序或句子中单词的排列方式自然语言形式语言我们使用产生规则来描述语言的语法上面的产生规则说明一个C语言的if语句的结构一个if然后一个(，某种表达式，再一个)最后是某种语句2022/11/12SEI22语法语言的语法是程序或句子中单词的排列方式2022/11/12022/11/12SEI23基本术语和概念有穷字母表∑一个符号的集合如ASCII、unicode、简体中文GB符号字母表∑中的元素如‘a’‘王’符号串由∑中的符号构成的一个有穷序列如”a”、”while”、”a=b+2”、”王者之风”2022/11/11SEI23基本术语和概念有穷字母表∑2022/11/12SEI24基本术语和概念空字ε不包含任何符号的序列不是空格如C语言中的""∑*∑上所有符号串的全体，ε也包含在其中如∑＝{a,b}，则∑*＝{ε,a,b,aa,bb,ab,ba,aaa,…}空集ø不包含任何元素的集合2022/11/11SEI24基本术语和概念空字ε基本术语和概念∑*的子集U和V的（连接）积定义为即集合UV中的符号串是由U和V的符号串连接而成的不满足交换律UV≠VU满足结合律(UV)W=U(VW)2022/11/12SEI25基本术语和概念∑*的子集U和V的（连接）积定义为2022/1基本术语和概念V自身的n次（连接）积记为V*称为V的闭包其中的每个符号串都是由V中的符号串经有限次连接而成的V+称为V的正则闭包2022/11/12SEI26基本术语和概念V自身的n次（连接）积记为2022/11/112022/11/12SEI27上下文无关文法文法描述语言的语法结构的形式规则（即语法规则）文法的作用句子生成：这个文法产生哪些句子？分析：一个句子S是否是这个文法产生的？上下文无关文法所谓上下文无关文法是这样一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境的2022/11/11SEI27上下文无关文法文法例：一个英语文法语法范畴2022/11/12SEI28例：一个英语文法语法范畴2022/11/11SEI28例：一个英语文法……S,NP,VP,N,Det,V非终结符John,Lisa,house,died,...终结符S开始符号例：一个英语文法……S,NP,VP,N,Det,例：句子产生从开始符号开始从右边选择一个非终结符X选择一条语法规则用γ代替X重复直到得到一个单词（字符）串例：句子产生从开始符号开始上下文无关文法一个CFG包括四个组成部分一组终结符号组成语言的基本符号，就是前面提到的单词符号终结符号从语法分析的角度看来是语言不可再分的基本符号一组非终结符号也称语法变量，用来代表语法范畴一个非终结符是一个类或集合记号，而不是一个个体记号一个开始符号特殊的非终结符，代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为句子一组产生式定义语法范畴的一种书写规则2022/11/12SEI31上下文无关文法一个CFG包括四个组成部分2022/11/11例：算术表达式文法2022/11/12SEI32自然语言描述变量是一个算术表达式若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式例：算术表达式文法2022/11/11SEI32自然语言描述2022/11/12SEI33上下文无关文法的形式定义形式上说，一个上下文无关文法G是一个四元式VT是一个非空有限集合，其中每个元素称为终结符号VN是一个非空有限集合，它的每个元素称为非终结符号，VT∩VN＝øS是一个非终结符号，称为开始符号P是一个产生式集合，每个产生式的形式是2022/11/11SEI33上下文无关文法的形式定义形式上2022/11/12SEI34上下文无关文法例：简单算术表达式的上下文无关文法可表示如下：VN={E}VT={+，*，(，)，－，i}S=EP:E→E+E (1)E→E*E (2)E→（E） (3)E→－E (4)E→i (5)（G2.1）该文法可以重写为：

E→E+E （1）

|E*E （2）

|（E）

（3）

|－E （4）

|i （5）（G2.2）

2022/11/11SEI34上下文无关文法例：简单算术表达2022/11/12SEI35文法和语言文法如何定义语言呢？从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。产生式E→(E)产生式E→E+E产生式E→i产生式E→i2022/11/11SEI35文法和语言文法如何定义语言呢？2022/11/12SEI36文法和语言直接推出推导最左推导、最右推导2022/11/11SEI36文法和语言直接推出推导最左推导2022/11/12SEI37文法和语言句型、句子、语言2022/11/11SEI37文法和语言句型、句子、语言文法、句子和句型示例例1：证明(i+i)是文法（G2.1）的句子证明：因为存在着如下推导E

E

(E)

(E+E)

(i+E)

(i+i)所以(i+i)是文法的句子。（证毕）出现在这个推导中的E,

E,(E),…,(i+i)都叫做这个文法的句型。2022/11/12SEI38文法、句子和句型示例例1：证明(i+i)是文法（G2.文法、句子和句型示例例2：文法G1定义的语言S→bAA→aA|a解答：可以分析得出L(G1)={ban|n≥1}例3：文法G2定义的语言S→ABA→aA|aB→bB|b解答：可以分析得出L(G2)={ambn|m,n≥1}2022/11/12SEI39文法、句子和句型示例例2：文法G1定义的语言2022/11文法、句子和句型示例例4：构造文法G3使得L(G3)={anbn|n≥1}解答：构造文法G3如下S→aSb|ab例5：构造文法G5使得L(G5)={anbm|n≥1,m≥0}解答：构造文法G5如下S→ABA→aA|aB→bB|ε

2022/11/12SEI40文法、句子和句型示例例4：构造文法G3使得2022/11/1简单程序语言文法……1是该文法的一个句子因为存在下面的推导简单程序语言文法……1是该文法的一个句子简单程序语言文法……2简单程序语言文法……22022/11/12SEI43文法和语言文法与语言之间并不存在一一对应的关系某一给定的文法可唯一确定它所产生的语言对于一个给定的语言来说，却往往可以用若干个不同的文法来产生文法的等价性设G1和G2是两个文法，若这两个文法产生同样的语言，即L(G1)=L(G2)，则称G1和G2等价。2022/11/11SEI43文法和语言文法与语言之间并不存2022/11/12SEI44语法分析树可以用图表示一个句型的推导，这种表示法称为语法分析树，简称语法树或分析树根节点的标记为文法开始符号；每个叶子节点由一个终结符标记；每个中间节点由一个非终结符标记如果有一步推导为

即我们使用了产生式

则语法分析（子）树的表示为2022/11/11SEI44语法分析树可以用图表示一个句型2022/11/12SEI45语法分析树一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。如果坚持使用最左（最右）推导，得到的语法树就完全等价于一个最左（最右）推导。由E最左推导(i+i)建立的语法树EEEEE()EEE()EEE+EE()EEE+iEE()EEE+ii2022/11/11SEI45语法分析树一棵语法树表示了一个语法分析树示例语法分析树示例2022/11/12SEI47二义性如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。二义性问题是不可判定的。不存在一个算法，能够在有限步内确切地判定一个文法是否为二义的。可以证明一个文法是有二义性的为文法的一个句子找到两个不同的最左推导（或最右推导，或语法树）文法的二义性不同于语言的二义性。可以对二义文法进行改写2022/11/11SEI47二义性如果一个文法存在某个句子二义性、优先级、结合性2022/11/12SEI48二义性、优先级、结合性2022/11/11SEI48构造无二义文法示例文法G2.1是二义的改写为无二义文法G2.32022/11/12SEI49E→E+E (1)E→E*E (2)E→（E） (3)E→－E (4)E→i (5)（G2.1）E→E+TE→T T→T*FT→F F→（E） F→－F F→i （G2.3）构造无二义文法示例文法G2.1是二义的2022/11/11S二义性、优先级、结合性构造无二义的表达式文法为每个优先级创建一个非终结符，如P1,P2,…,Pn，其中Pn的优先级最高对优先级为i的运算符op如下构造产生式如果op是左结合的，则产生式为

Pi

→PiopPi+1

|Pi+1如果op是右结合的，则产生式为Pi

→Pi+1opPi

|Pi+1对于初等表达式如数字、标识符、括号等，创建非终结符Pn+1，构造产生式为

Pn+1

→num|id|(P1)2022/11/12SEI50二义性、优先级、结合性构造无二义的表达式文法2022/11/2022/11/12SEI51化简了的文法文法中不含任何下面形式的产生式：P→P每个非终结符P必须都有用2022/11/11SEI51化简了的文法文法中不含任何下面2022/11/12SEI522.4形式语言鸟瞰乔姆斯基（Chomsky）给出了文法的定义：G＝（VN,VT,P,S）（VN

∩VT=，VN∪VT=V）对产生式的形式给以不同的限制可定义四类基本文法，分别称为0型文法，1型文法，2型文法，3型文法。2022/11/11SEI522.4形式语言鸟瞰乔姆斯基（2022/11/12SEI532.4形式语言鸟瞰四类文法描述语法的能力从0型文法开始依次减弱k型语言类Lk必然是k-1型语言类Lk-1的子类(其中,k=1,2,3)存在这样的k型语言，它不能由任何k+1型文法来描述(其中，k=0,1,2)2022/11/11SEI532.4形式语言鸟瞰四类文法描本章小结本章小结本章小结55本章小结552022/11/12SEI56课后作业阅读教材2.2节高级语言的一般特性重点阅读2.3节程序语言的语法描述做习题教材p35第4题教材p366,7,8,9,10,112022/11/11SEI56课后作业阅读教材高级语言及其语法描述西北大学软件工程研究所龚晓庆高级语言及其语法描述西北大学软件工程研究所龚晓庆2022/11/12SEI58Contents程序语言的定义1高级语言的一般特性2上下文无关文法3形式语言42022/11/11SEI2Contents程序语言的定义12022/11/12SEI592.1程序语言的定义一个程序语言是一个记号系统如同自然语言一样，程序主要由语法和语义两个方面定义语法描述程序中单词的排列方式或结构语义描述程序的含义有时候语言定义也包含语用信息语用主要是有关程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界（如数学或计算机的对象和操作）联系起来2022/11/11SEI32.1程序语言的定义一个程序语2022/11/12SEI60语法任何语言程序都可以看作是一定字符集（字母表）上的字符串合式的程序形式上正确的程序所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序这些规则的一部分称为词法规则另一部分称为语法规则（产生规则）词法规则和语法规则规定了程序的形式结构，是判断输入字符串是否构成一个合式程序的依据。2022/11/11SEI4语法任何语言程序都可以看作是一定2022/11/12SEI61词法规则单词符号单词符号是语言中具有独立意义的最基本结构常数、标识符、基本字、算符、界符词法规则是指单词符号的形成规则描述和分析的工具有限自动机（FiniteAutomata）正规表达式正规文法2022/11/11SEI5词法规则单词符号2022/11/12SEI62语法规则语法范畴（语法单位）表达式、语句、过程、程序语法规则是语法单位的形成规则，它规定了如何从单词符号形成更大的结构，即语法单位。描述工具上下文无关文法（Context-FreeGrammar，CFG）2022/11/11SEI6语法规则语法范畴（语法单位）2022/11/12SEI63语义所谓一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则语义规则的描述没有公认的形式系统现常用属性文法2022/11/11SEI7语义所谓一个语言的语义是指这样的2022/11/12SEI64程序语言和程序程序语言的基本功能描述数据和对数据的运算程序所谓一个程序，从本质上说是描述一定数据的处理过程2022/11/11SEI8程序语言和程序程序语言的基本功能2022/11/12SEI65程序的层次结构程序子程序或分程序语句数据引用表达式算符函数调用2022/11/11SEI9程序的层次结构程序子程序或分程序2022/11/12SEI662.2高级语言的一般特性高级语言的分类1程序结构2数据类型和数据结构3语句与控制结构42022/11/11SEI102.2高级语言的一般特性高级2022/11/12SEI67高级语言的分类强制式语言命令驱动，面向语句应用式语言函数式语言，LISP基于规则的语言检查条件，执行动作，Prolog面向对象语言封装，继承，多态2022/11/11SEI11高级语言的分类强制式语言2022/11/12SEI68程序结构示例过程式程序FORTRANPascal基于对象/面向对象程序AdaJava2022/11/11SEI12程序结构示例过程式程序2022/11/12SEI69数据类型与操作数据类型的三要素用于区别这种类型数据的属性这种类型的数据对象可以具有的值可以作用于这种类型的数据对象的操作数据类型初等数据类型数据结构抽象数据类型2022/11/11SEI13数据类型与操作数据类型的三要素2022/11/12SEI70初等数据类型数值数据整数，实数；可以进行算术运算逻辑数据逻辑型数据，位串；字符数据字符和字符串指针类型2022/11/11SEI14初等数据类型数值数据2022/11/12SEI71标识符和名字标识符程序中的各种名字都用标识符表示标识符的构成规则名字具有明确的意义和属性存储单元、值类型、作用域2022/11/11SEI15标识符和名字标识符2022/11/12SEI72数据结构数组下标、下标变量数组的存放方式与元素地址记录字段，域存放方式与边界对齐其它字符串、表、栈2022/11/11SEI16数据结构数组2022/11/12SEI73抽象数据类型抽象数据类型包括数据对象的一个集合作用于这些数据对象的抽象运算的集合这种类型对象的封装2022/11/11SEI17抽象数据类型抽象数据类型包括2022/11/12SEI74语句与控制结构表达式变量、常数是表达式；若E1、E2为表达式，θ是一个二元算符，则E1θE2是表达式；若E是表达式，θ是一元算符，则θE（或Eθ）是表达式；若E是表达式，则（E）是表达式。算符操作数个数、优先级、结合性2022/11/11SEI18语句与控制结构表达式例——C语言运算符例——C语言运算符2022/11/12SEI76语句按功能分类说明性语句执行性语句赋值、控制、输入输出按形式分类简单语句复合语句2022/11/11SEI20语句按功能分类2022/11/12SEI772.3程序语言的语法描述上下文无关文法1文法和语言2推导、语法分析树3二义文法42022/11/11SEI212.3程序语言的语法描述上下语法语言的语法是程序或句子中单词的排列方式自然语言形式语言我们使用产生规则来描述语言的语法上面的产生规则说明一个C语言的if语句的结构一个if然后一个(，某种表达式，再一个)最后是某种语句2022/11/12SEI78语法语言的语法是程序或句子中单词的排列方式2022/11/12022/11/12SEI79基本术语和概念有穷字母表∑一个符号的集合如ASCII、unicode、简体中文GB符号字母表∑中的元素如‘a’‘王’符号串由∑中的符号构成的一个有穷序列如”a”、”while”、”a=b+2”、”王者之风”2022/11/11SEI23基本术语和概念有穷字母表∑2022/11/12SEI80基本术语和概念空字ε不包含任何符号的序列不是空格如C语言中的""∑*∑上所有符号串的全体，ε也包含在其中如∑＝{a,b}，则∑*＝{ε,a,b,aa,bb,ab,ba,aaa,…}空集ø不包含任何元素的集合2022/11/11SEI24基本术语和概念空字ε基本术语和概念∑*的子集U和V的（连接）积定义为即集合UV中的符号串是由U和V的符号串连接而成的不满足交换律UV≠VU满足结合律(UV)W=U(VW)2022/11/12SEI81基本术语和概念∑*的子集U和V的（连接）积定义为2022/1基本术语和概念V自身的n次（连接）积记为V*称为V的闭包其中的每个符号串都是由V中的符号串经有限次连接而成的V+称为V的正则闭包2022/11/12SEI82基本术语和概念V自身的n次（连接）积记为2022/11/112022/11/12SEI83上下文无关文法文法描述语言的语法结构的形式规则（即语法规则）文法的作用句子生成：这个文法产生哪些句子？分析：一个句子S是否是这个文法产生的？上下文无关文法所谓上下文无关文法是这样一种文法，它所定义的语法范畴是完全独立于这种范畴可能出现的环境的2022/11/11SEI27上下文无关文法文法例：一个英语文法语法范畴2022/11/12SEI84例：一个英语文法语法范畴2022/11/11SEI28例：一个英语文法……S,NP,VP,N,Det,V非终结符John,Lisa,house,died,...终结符S开始符号例：一个英语文法……S,NP,VP,N,Det,例：句子产生从开始符号开始从右边选择一个非终结符X选择一条语法规则用γ代替X重复直到得到一个单词（字符）串例：句子产生从开始符号开始上下文无关文法一个CFG包括四个组成部分一组终结符号组成语言的基本符号，就是前面提到的单词符号终结符号从语法分析的角度看来是语言不可再分的基本符号一组非终结符号也称语法变量，用来代表语法范畴一个非终结符是一个类或集合记号，而不是一个个体记号一个开始符号特殊的非终结符，代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为句子一组产生式定义语法范畴的一种书写规则2022/11/12SEI87上下文无关文法一个CFG包括四个组成部分2022/11/11例：算术表达式文法2022/11/12SEI88自然语言描述变量是一个算术表达式若E1和E2是算术表达式，则E1+E2、E1*E2和(E1)也是算术表达式例：算术表达式文法2022/11/11SEI32自然语言描述2022/11/12SEI89上下文无关文法的形式定义形式上说，一个上下文无关文法G是一个四元式VT是一个非空有限集合，其中每个元素称为终结符号VN是一个非空有限集合，它的每个元素称为非终结符号，VT∩VN＝øS是一个非终结符号，称为开始符号P是一个产生式集合，每个产生式的形式是2022/11/11SEI33上下文无关文法的形式定义形式上2022/11/12SEI90上下文无关文法例：简单算术表达式的上下文无关文法可表示如下：VN={E}VT={+，*，(，)，－，i}S=EP:E→E+E (1)E→E*E (2)E→（E） (3)E→－E (4)E→i (5)（G2.1）该文法可以重写为：

E→E+E （1）

|E*E （2）

|（E）

（3）

|－E （4）

|i （5）（G2.2）

2022/11/11SEI34上下文无关文法例：简单算术表达2022/11/12SEI91文法和语言文法如何定义语言呢？从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。产生式E→(E)产生式E→E+E产生式E→i产生式E→i2022/11/11SEI35文法和语言文法如何定义语言呢？2022/11/12SEI92文法和语言直接推出推导最左推导、最右推导2022/11/11SEI36文法和语言直接推出推导最左推导2022/11/12SEI93文法和语言句型、句子、语言2022/11/11SEI37文法和语言句型、句子、语言文法、句子和句型示例例1：证明(i+i)是文法（G2.1）的句子证明：因为存在着如下推导E

E

(E)

(E+E)

(i+E)

(i+i)所以(i+i)是文法的句子。（证毕）出现在这个推导中的E,

E,(E),…,(i+i)都叫做这个文法的句型。2022/11/12SEI94文法、句子和句型示例例1：证明(i+i)是文法（G2.文法、句子和句型示例例2：文法G1定义的语言S→bAA→aA|a解答：可以分析得出L(G1)={ban|n≥1}例3：文法G2定义的语言S→ABA→aA|aB→bB|b解答：可以分析得出L(G2)={ambn|m,n≥1}2022/11/12SEI95文法、句子和句型示例例2：文法G1定义的语言2022/11文法、句子和句型示例例4：构造文法G3使得L(G3)={anbn|n≥1}解答：构造文法G3如下S→aSb|ab例5：构造文法G5使得L(G5)={anbm|n≥1,m≥0}解答：构造文法G5如下S→ABA→aA|aB→bB|ε

2022/11/12SEI96文法、句子和句型示例例4：构造文法G3使得2022/11/1简单程序语言文法……1是该文法的一个句子因为存在下面的推导简单程序语言文法……1是该文法的一个句子简单程序语言文法……2简单程序语言文法……22022/11/12SEI99文法和语言文法与语言之间并不存在一一对应的关系某一给定的文法可唯一确定它所产生的语言对于一个给定的语言来说，却往往可以用若干个不同的文法来产生文法的等价性设G1和G2是两个文法，若这两个文法产生同样的语言，即L(G1)=L(G2)，则称G1和G2等价。2022/11/11SEI43文法和语言文法与语言之间并不存2022/11/12SEI100语法分析树可以用图表示一个句型的推导，这种表示法称为语法分析树，简称语法树或分析树根节点的标记为文法开始符号；每个叶子节点由一个终结符标记；每个中间节点由一个非终结符标记如果有一步推导为

即我们使用了产生式

则语法分析（子）树的表示为2022/11/11SEI44语法分析树可以用图表示一个句型2022/11/12SEI101语法分析树一棵语法树表示了一个句型种种可能的（但未必是所有的）不同推导过程，包括最左（最右）推导。如果坚持使用最左（最右）推导，得到的语法树就完全等价于一个最左（最右）推导。由E最左推导(i+i)建立的语法树EEEEE()EEE()EEE+EE()EEE+iEE()EEE+ii2022/11/11SEI45语法分析树一棵语法树表示