语言结构与文法

《语言结构与文法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章语言结构与文法目的：为复杂的语言结构的分析提供精确、严格的描述方法用途：支持语言结构（语法、词法）的抽象分析指导分析程序的实现约束假设：不考虑语义信息及其用途仅考虑语言的组成结构计算机语言与自然语言的比较自然语言是人与人的通讯工具环境、背景知识、语气、二义性计算机语言计算机软件使用的通讯工具严格的语法、语义2.1计算机语言的组成语言的组成语言：句子的集合句子：多个单词按一定规则组成单词：多个字符按一定规则组成程序设计语言编程语言程序的集合程序：多个单词按语法规则组成单词：多个字符按词法规则组成计算机语言的共同

2、点语法：语句的组成规则描述方法：BNF范式、语法描述图词法：单词的组成规则描述方法：BNF范式、正规式单词：具有语义的最小字符串（可区分的）语言的描述方法叙述性方法自然语言（非形式化描述）记号方法数学方法（形式化描述）保证描述清晰准确形式化描述的作用理论基础和抽象分析方法2.2文法：提供语言结构的形式化描述分析语言组成结构的规律语言是句子的集合句子是按一定规则构成的符号串语言有一组基本符号例2-1语言结构ＢＮＦ范式描述句子的组成规则α∷＝β（简写为产生式α→β）α、β表示若干个终结符或非终结符终结符：基本符号集非终

3、结符：某个语言结构文法G的形式定义Ｇ=(ＶT，ＶN，Ｐ，Ｓ)Chomsky定义文法为一个四元组ＶT：终结符集ＶN：非终结符集Ｐ：有穷的产生式集合Ｓ：开始符号∈ＶN至少在产生式左侧出现一次例2-2运算表达式的文法G考虑所有运算表达式组成的语言G=({i，+，*，(，)}，{E}，P，E)P:E→E+EE→E*EE→(E)E→i运算表达式的描述简写的文法E→E+E

4、E*E

5、(E)

6、i语义E表示表达式i表示整数开始符号表示整个句子所描述的语言所有仅包含乘法和加法的整数运算表达式直接推导的定义用某个产生式的右部代替左部当Ａ

7、→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，（表示0个或多个终结符或非终结符组成的符号串）称符号串αγβ是αＡβ的直接推导，记为αＡβ=>αγβ例：i+E=>i+E*EE=>(E)推导的定义：α0=>α1=>α2=>…=>αn记为α0=+>αn（一步或多步）α0=*>αn（零步或多步）例：E=>(E)=>…=>(i+E)记为E=+>(i+E)最左推导、最右推导每次直接推导中代换最左（右）的非终结符合法句子的生成从开始符号Ｓ出发反复推导，每次得到一个句型，最终得到句子（完全由终结符组成句型）合法句子的验证通

8、过基于文法的推导，可判断出给定的符号串是否是属于该文法描述的语言文法的作用提供了严格的抽象分析手段支持语法错误检查的实现语言由所有合法句子组成G描述的所有合法运算表达式例:表达式i+i*i的生成E=>E+E=>i+E句型=>i+E*E=>i+i*E=>i+i*i句子语言L的形式定义Ｌ(Ｇ)＝{α｜Ｓ＝+＞αandα∈ＶT*}由文法Ｇ产生的所有句子的集合文法G的作用以有限的规则描述无限的语言现象有限：产生式集合终结符集合非终结符集合无限：由开始符号导出的句子2.3分析树ParseTree用树的形式表示句子的结构树根：

9、开始符号中间结点：非终结符叶结点：终结符每个推导对应一个中间结点及其儿子表示精确的文法分析结果例2-3表达式i+i*i的分析树(按照例1-2的文法）二义性文法对同一句子存在两棵语法分析树在理论上不可判定2.4文法的分类(Chomsky)表述语言结构的复杂程度涉及文法的复杂程度、分析方法的选择文法Ｇ的每个产生式α→β中：若α∈(ＶN∪ＶT)*且至少包含一个非终结符,β∈(ＶN∪ＶT)*则Ｇ是０型文法。上下文有关文法若产生式α→β的集合中除Ｓ→ε外所有｜α｜≤｜β｜，ε代表空串｜α｜表示α中符号的个数并且S不出现在β中

10、，则Ｇ是１型文法即：上下文有关文法上下文无关文法若α∈ＶN，β∈(ＶN∪ＶT)*则Ｇ是２型文法即：上下文无关文法例：例1-2中的运算表达式程序设计语言的多数语法特征正规文法右线性文法（Ａ、Ｂ∈ＶN，ａ∈ＶT*）若产生式为Ａ→ａＢ或Ａ→ａ左线性文法若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）例：程序设计语言的多数词法特性2.5文法的应用明确描述对象──语言合法的语言结构确定基本符号集ＶT引入非终结符各种句子结构定义句子的组成规则用BNF范式或产生式例2-3描述电话号码的格式常用：67391742010-67

11、391742(010)673917421）描述对象：电话号码（开始符号)包括地区代码、局代码、本机代码不包括分机、呼机、手机、国际代码形式化过程2）基本符号集（终结符）：数字字符DIG、分割符-、（、）3）引入非终结符：描述对象及其组成部分：电话号码地区代码、局代码、本机代码定义组成规则<电话号码>→<局代码><本机码><电话号码>→<区前缀><局代码><本