语法分析
Syntax Analysis语法分析器:syntactic analysis
parsing
是根据某种给定的形式文法对由单词序列(如英语单词序列)构成的输入文本进行分析并确定其语法结构的一种过程。
语法分析器(parser)通常是作为编译器或解释器的组件出现的,它的作用是进行语法检查、并构建由输入的单词组成的数据结构(一般是语法分析树、抽象语法树等层次化的数据结构)。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”,并将单词流作为其输入。实际开发中,语法分析器可以手工编写,也可以使用工具(半)自动生成.语法分析器的任务主要是确定是否可以以及如何从语 法的起始符号推导出输入符号串(输入文本),主要可以通过两种方式完成:
- 自顶向下分析:根据形式语法规则,在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。
- 自底向上分析:语法分析器从现有的输入符号串开始,尝试将其根据给定的形式语法规则进行改写,最终改写为语法的起始符号。
文法
程序语言是符号语言,即一个记号系统,它主要有语法、语义和语用等三方面定义。
文法语言中的每个句子可以用严格定义的规则来构造,通俗地讲就是根据一些指定的规则来确定编程语言的语法从而实现编译器的功能.
语法:是对语言结构的定义(什么样的符号序列是合法的)。任何语言程序都可看成是一定字符集上的一字符串(有限序列),语法定义语言的词法和语法的形式规则。
字母表是一个有限的字符集,字符集中的字符是语言程序中可能出现的字符,它们是语言程序单词的组成部分。 词法规则定义了语言程序中单词符号的形成规则。即什么样的字符串是一个合法的单词。如标识符、数值常量、运算符等单词的构成规则。 语法规则定义了语言程序中语法单位的形成规则。一般语言的语法单位有表达式、语句、分程序、函数、过程和程序等。描述语法规则和进行语法分析的有效工具是上下文无关文法。 语义:描述语言的含义;定义语言的单词符号和语法单位的意义。目前编译程序中常用的语义分析方法是一种基于属性文法的语法制导翻译。即在语法分析的同时对其中识别出的语法单位进行语 义的分析与翻译工作;在描述文法的同时为定义的语法范畴加上它们的属性计算规则,属性可以是语法范畴的类型、地址、取值、执行动作等信息。
语用:是从使用的角度去描述语言。定义程序设计技术和语言成分的使用方法,它使语言的基本概念与语言的外界(如数学概念或计算机的对象和操作)联系起来
字母表(alphabet):字母表是元素的非空有穷集合,任何语言的字母表指出了该语言中允许出现的一切符号。
∑ = {a,b,c}
- ∑是字母表,由 a,b,c 三个元素组成。 C 语言的字母表是字母、数字和若干专用符号组成。
- 符号(symbol):字母表中的元素称为符号,或称为字符。 a,b,c 是字母表 ∑ 中的符号。
- 符号串(string):符号的有穷序列称为字符串。符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。不包含任何符号的 符号串,称为空符号串,用表示 (a,b,ab,ba,cba,abc 等都是字母表∑上的符号串)
运算
-
符号串的连结
catenation
设 x 和 y 是符号串,则串 xy 称为它们的连结。x = abc
,y = 10a
,则xy = abc10a
,yx = 10aabc
.特别,对任意一符号串 x 有: -
集合的乘积
product
设 A 和 B 是符号串的集合,则 A 和 B 的乘积定义为:AB = {xy | x ∈ A, y ∈ B}
设 A = {a,b}, B = {c,d}则 AB = {ac,ad,bc,bd}
空集Φempty set
:Φ表示不含任何元素的空集 { } -
符号串的幂运算
power
设 x 是符号串,则 x 的幂运算定义为: -
集合的幂运算同理,只不过
-
集合A的正闭包A+与闭包A
设 A 是符号串的集合,则集合 A 的正闭包 A+ 和闭包 A* 定义为:
设 ,则