yi

09 蘇える巨神兵

简单的一遍编译器

• 程序设计语言的定义
  • 语法 上下文无关/BNF范式
  • 语义 非形式化方法/启发性实例

上下文无关

• stmt -> if(expr) stmt else stmt
  • 终结符集合
  • 非终结符集合
  • 产生式集合
  • 特殊的终结符 - 开始符号

Exercise2.2

2.2.1

S -> SS+|SS*|a

1. a是S，所以aa+是一个S，所以aa+a*是一个S
2. 
3. 仅仅带有加减的后缀表达式

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 (2¹ + 2⁰) * 2ⁿ + Σ_m (2³ + 2²) * 2^m
= Σ_n 3 * 2 ⁿ + Σ_m 9 * 2^m