program language

1. 概述

描述语言的难题之一是 所有人都必须能理解这种描述

类似自然语言,程序语言描述分为 语法和语义

有时候语法不同,但是代表的语义相同。例如 count++count=count+1

语言是句子的集合,而句子是由字符表中的字符组成的串。英语的句子是由 26 个字母组成的串,而程序语言的句子是由 ASCII 字符组成的串。

语言有两种描述模型,分别是

  1. 语言识别器:有限自动机、下推机。例如编译器。
  2. 语言生成器:正则文法、上下文无关文法。例如形式定义。

2. 语法的形式化定义

上下文无关文法 G 是一个四元组(V,T,P,S),其中


语法定义需要严格地定义程序的复杂结构。在定义 Algol 60 语言时,Backus 提出了一种形式化的语法定义方式,称为 BNF 范式。

BNF 提供了两类符号:终结符和非终结符

一个非终结符表示语言中的一个语法类,例如

一个语言的 BNF 语法定义由一组产生式(或规则) 组成,本质上是一个上下文无关文法

产生式的形式是:左部→右部

一个简单的文法如下:

<program> -> <stmts>
<stmts> -> <stmt> | <stmt>;<stmts>  // 用递归扫描列表
<stmt> -> <var> = <expr>
<var> -> a | b | c | d
<expr> -> <term>+<term> | <term>-<term>
<term> -> <var> | const

推导 是一个或一系列产生式的应用,最后得到一个全是终结符的语言。一个可能的推到如下

<program>                // 所用产生式
=> <stmts>               // <program> -> <stmts>
=> <stmt>                // <stmts> -> <stmt>
=> <var> = <expr>        // <stmt> -> <var>=<expr>
=> a = <expr>            // <var> -> a
=> a = <term>+<term>     // <expr> -> <term>+<term>
=> a = <var>+<term>      // <term> -> <var>
=> a = b+<term>          // <var> -> b
=> a = b+const           // <term> -> const

句型:由开始符号经过推导得到的字符串。例如 a=b+<term>

句子:只含有终结符的句型。例如 a=b+const

最左推导:每次总是替换句型最左边的非终结符。例如

<program> => <stmts> => <stmt> => <var> = <expr>
 => a = <expr> => a = <term> + <term>=> a = <var> + <term>
 => a = b + <term> => a = b + const 

最右推导:每次总是替换句型最右边的非终结符。

<program> => <stmts> => <stmt> => <var> = <expr>
=> <var> = <term> + <term> => <var> = <term> + const 
=> <var> = <var> + const => <var> = b + const => a = b + const

推导过程一直进行到句型不包含非终结符为止,即生成句子为止。

除了最左、最右推导,还有既不是最左也不是最右推导。

推导的顺序对文法生成的语言没有影响,但可以生成语言的不同句子。

穷举所有选择的组合,可以生成完整的语言。

同大多数语言一样,这种语言通常是无限的,无法在有限的时间内生成语言中的所有句子。

<赋值> -> <标识符> = <表达式>
<标识符> -> A | B | C
<表达式> -> <标识符> + <表达式>
           | <标识符> + <表达式>
           | <标识符> * <表达式>
           | (<表达式>)
           | <标识符>

语法树:推导的分层结构(或树型结构)表示。前面例子中的 a=b+const 的语法树如下

语法树

最左推导:最左遍历

最右推导:最右遍历(这两个特点可以用编程实现一下)


二义性:文法生成的句型有两个或多个语法树。

因此,我们用不同的非终结符表示不同的优先级。利用如下产生式生成的句子 const-const/const 就是无二义性的

<expr> -> <expr> - <term> | <term> 
<term> -> <term> / const | const 

无二义性

除了优先级,结合性也会出现二义性。

二义:<expr> -> <expr> + <expr> | const 
非二义:<expr> -> <expr> + const | const 

拓展的 BNF(EBNF):增加可读性和可写性,并没有增加表达能力。

BNF 和 EBNF 的功能上是一样的,所以它们之间是可以互相转换的。例如下面的 BNF 和 EBNF 都是表达同一套产生式。

// BNF 右结合
<expr> -> <expr> + <term> 
               | <expr> - <term> 
               | <term> 
<term> -> <term> * <factor> 
               | <term> / <factor> 
               | <factor> 
// NBNF
<expr> -> <term> {(+ | -) <term>} 
<term> -> <factor> {(* | /) <factor>}

3. 属性文法

有些语言的结构特点很难用 BNF 描述,例如

这类语言规则称为静态语义规则。

Knuth 在 1968 年提出了属性文法。


例如:形如 id=id+id 的赋值语句。

而其 BNF 如下,并不能进行类型判断。

<ass_stmt>-><var>=<expr>
<expr> -> <var> + <var> 
<var> -> id 

为了满足上述要求,我们需要知道

这些需要求解的信息称之为语义属性,简称属性。属性文法是具有以下附加特性的文法。

每个文法符号 X 都有一个属性集 A(X) 。

每条产生式有一个计算属性的语义函数集。

每条产生式有一个分析静态语义可能为空的谓词函数集。

在前面的例子中,实际类型是与 <var><expr> 相关的综合属性,以及 id 的本质属性。期望类型是与 <expr> 相关的继承属性。

我们完善前面的 BNF 产生式,得到如下

<ass_stmt>-><var>=<expr>
函数:<expr>.expected_type = <var>.actual_type    // 从左往右继承属性
<expr> -> <var>[1] + <var>[2]
函数:<expr>. actual_type = <var>[1].actual_type   // 自底向上综合属性
谓词: <var>[1]. actual_type == <var>[2].actual_type
      <expr>. expected_type == <expr>.actual_type
<var> -> id
函数:<var>.actual_type = id.actual_type          // 自底向上的综合属性
     id.actual_type = lookup(符号表,id)           // 本质属性一开始就要声明

关于属性的判断的时候,自己的脑子里面要有一颗文法树。

属性文法的计算就是语法树的装饰过程。

只有综合属性:自底向上

只有继承属性:自顶向下(从左到右)

两者都有:自底向上和自顶向下

个人理解:不论哪种形式遍历得到属性,最后都要校验一次,看看会不会冲突,如果冲突说明代码出现问题了。

4. 动态语义

动态语义:编程语言中表达式、语句和程序单元的意义。目前没有被普遍接受的统一的形式。常用的三种语义描述如下

4.1 操作语义

用抽象的方法描述语句的 执行效果 ,以免语义依赖于语言实现所用的具体计算机。大概步骤如下:

  1. 设计一个抽象机及其状态。
  2. 定义每一个语句(或抽象机指令)对状态的改变。

人工智能之父 John McCarthy 用 Lisp 语言本身定义了 Lisp 语言的执行过程(语义)。

描述机器状态最简单的形式化模型:从合法名字集合到 ”值“ 的映射。

其形式化定义为:$S: Name \rightarrow Value U \lbrace \perp \rbrace$

其中 S 表示一个状态,Name 表示名字的集合,Value 表示 “值” 的集合,$\lbrace\perp\rbrace$ 表示无定义的一些符号。


接下来我们用下面的实例语言的 BNF 来描述不同语句的执行效果。

<stmt> -> SKIP
	| <var> = val
	| <stmt>;<stmt>
	| IF <cond> THEN <stmt> ELSE <stmt>
	| WHILE <cond> DO <stmt> END

  1. SKIP 语句的操作语义:SKIP 语句不做任何操作

    SKIP, S => S
    
  2. <stmt>, S1 => S2 :表示在状态 S1 下执行语句 <stmt> 后,状态改变为 S2 。

  3. 赋值语句 <val>=val 的操作语义:将变量 <var> 的值改为 val ,其他变量不变。例如

    x=2,{x -> 3, y -> 5, z -> 0} => {x -> 2, y -> 5, z -> 0}
    x=2, {y->1} => {x -> 2, y-> 1}
    

如果有多个语句(复合语句),则先执行语句1,再执行语句2

stmt1, S => S1	stmt2, S1 => S2
等价于
stmt1;stmt2, S => S2

例如

x=2; z=3, {x->1} => {x->2, z->3}