明 光 大 正

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. 仅仅带有加减的后缀表达式
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

页阅读量:  ・  站访问量:  ・  站访客数: