Skip to content

Compiler_Notes.md

Latest commit

 

History

History
210 lines (114 loc) · 5.28 KB

Compiler_Notes.md

File metadata and controls

210 lines (114 loc) · 5.28 KB
Raw

...menustart

...menuend

Compiler Note

Introduction

2 parts of compiler : analysis / synthesis

lexical analysis ，or scanning

  • tokens and symbol table

Syntax analysis , or parsing

  • syntax describes the proper form of its programs
  • use context-free grammars to specify the syntax of a language
    • CFG itself is specified by listing their productions.
    • Parser的任务是 find a parse tree for a given string of terminals

Concrete syntax tree

  • derivation 的过程

    • root -- start symbol
    • interior node -- nonterminal
      • correspond to a production with its children
    • leaf -- terminal or eps
      • from left to right, the leaves form the yield of the tree

  • CST 其实就是 parse tree。

  • CST只是概念上的语法术，大部分编译器都使用AST。

(abstract) syntax tree

  • interior -- an operator
  • children of the node -- the operands of the operator
  • AST 是一种数据结构

Precedence of Operators 操作符优先级

  • Idea to any number n of precedence levels
    • We need n+1 nonterminals.
    • The first,like factor , can never be torn apart.
    • Then, for each precedence level, there is one nonterminal representing expressions that can be torn apart only by operators at that level or higher

syntax-directed translation (SDT)

  • 将输入的字符串翻译成一些列具有语义的动作
  • SDT is done by attaching rules or program fragments to productions in a grammar.

Syntax-directed definition

  • SDD是特殊的CFG , 特殊之处在于:
    • We associate attributes with nonterminals and terminals.
    • Then, we attach rules to the productions of the grammar;
PRODUCTION SEMANTIC RULES
expr → expr₁ + term expr.t = expr₁.t ‖ term.t ‖ '+'

Syntax-directed Translation Schemes

  • SDTS 也是一种特殊的CFG
    • it attachs program fragments to productions in a grammar.
  • SDTS 和 SDD 相似，SDD指定语义动作，SDTS实现了这些语义动作。 ??
expr → expr₁ + term  {print('+')}
expr → expr₁ - term  {print('-')} 
expr → term
term → 0             {print('0')}

Parsing

  • Parsing is the process of determining how a string of terminals can be generated by a grammar.
  • "recursive descent" method can be used both to parse and to implement syntax-directed translators.
  • Yacc is a alternative tool
    • to generate a translator directly from a translation scheme

Top-Down Parsing

  • 可以较容易地手工构造出高效的语法分析器

Bottom-up Parsing

  • can handle a larger class of grammars and translation schemes
    • software tools for generating parsers directly from grammars often use bottom-up methods.

Predictive Parsing

  • a simple form of recursive-descent parsing
    • the lookahead symbol unambiguously determines the flow of control
  • is a program consisting of a procedure for every nonterminal
  • FIRST(α)

Semantic analysis

  • semantic define what its programs mean
  • gather type info
  • type checking
  • coercions

Intermediate code generation

  • AST -> three-address code

--- analysis end ---

Code optimize

Code generation