程序语言的语法描述

文档状态：编辑中....

Table of Contents

区分

字母&字(字符串)&空字

文法推导

文法<=>语言

最左推导,最右推导

语法树

二义性

文法的二义性

对于同一种语言有多颗语法树

语言的二义性

存在描述的语言的一个无二义性的文法

chomsky的语言体系

从0-3型差异在推导规则上,从对左侧的限制到对右侧的限制,像如果想要使用上下文无关文法
左侧需要变成一个否则左侧出现依赖行为,总而言之,这里描述的不够详细,0型的描述能力最强但是比较复杂,3型比较简单但是能力有限,我们通常使用2型,技术成熟,对于2型无法做到的,通常使用一些奇技淫巧比如说符号表等小东西去实现0型或1型才能实现的东西,比如 标识符引用或者过程调用过程中的形实参对应性(个数,顺序和类型一致性)

0型(短语文法 图灵机)

１型(上下文有关文法 线性界限自动机)

2型(上下文无关文法 非确定下推自动机)

3型(正规文法有限自动机)

1型文法是0型文法的特例,2型文法是1型文法的特例
0----+限制--->1型----+限制--->2型----+限制--->3型