yi
09 蘇える巨神兵
简单的一遍编译器
- 程序设计语言的定义
- 语法 上下文无关/BNF范式
- 语义 非形式化方法/启发性实例
上下文无关
- stmt -> if(expr) stmt else stmt
- 终结符集合
- 非终结符集合
- 产生式集合
- 特殊的终结符 - 开始符号
Exercise2.2
2.2.1
S -> SS+|SS*|a
- a是S,所以aa+是一个S,所以aa+a*是一个S
- 仅仅带有加减的后缀表达式
2.2.2
- a) S -> 0S1 | 01
- 前面n个0,后面n个1,n>=1
- b) S -> +SS | -SS | a
- 仅仅带有加减的前缀表达式
- c) S -> S(S)S| null
- 匹配任意范围和递归层数的括号
- d) S -> aSbS | bSaS | null
- 拥有相同数量的a和b
- e) S -> a | S+S | SS | S* |(S)
- ?
2.2.4
- 1.Arithmetic expressions in postfix notation.
- E -> E E operation | num
- 2.Left-associative lists of identifiers separated by commas.
- list -> list , id | id
- 3.Right-associative lists of identifiers separated by commas.
- list -> id , list | id
- 4.Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.
- d -> d+g | d-g | g
- g -> base*g | base/g | base
- base -> id | num | *
- 5.Add unary plus and minus to the arithmetic operators of 4.
- d -> d+g | d-g | g
- g -> g*tmp| g/tmp | tmp
- tmp -> +base | -base | base
- base -> id | num | *
2.2.5
- num -> 11 | 1001 | num0 | num num
- 证明以此构成的二进制数是可以被3整除的
sum
= Σn (21 + 20) * 2n + Σm (23 + 22) * 2m
= Σn 3 * 2 n + Σm 9 * 2m