Friday, March 5, 2010

Building a simple compiler Series (1)

I have a plan this year, which is trying to write a simple compiler by myself. I know it sounds crazy, but I think it's would be fun, and it would be very helpful for deeply understanding some low level of the machine,and also can help improve my programming skill. There is a populer computer science book which is called "Dragon book". I am reading it now, and will take note about it. Do it,  it's not so hard as you think.
Syntax Definition
stmt-> if (expr) stmt else stmt
-> may be read as "can have the form", this rule is called a production. In a production ,lexical element like the keyword if and the parentheses are called terminals, variables like expr and stmt represent sequences of terminals are called nonterminals
Definition of Grammars:
A context-free grammar has four components:
  1. A set of terminal symbols
  2. A set of nonterminals
  3. A set of production
  4. A designation of one of the nonterminals as the start symbol
Parsing is the problem of taking a string of terminals and figuring out how to derive it from the start symbol of the grammar, and if it cannot be derived from the start symbol of the grammer.
Parse Tree
  1. The root is labeled by the start symbol
  2. Each leaf is labeled by a terminal or by empty string
  3. Each interior node is labeled by a nonterminal
Associativity of Operators
In most programming language the four arithmetic operators, addition,substraction,multiplication,and division are left-associative.
Syntax-Directed Translation
  • Attributes.An Attributes is any quantity associated with a programming construct.Examples of attributes are data types of expressions, the number of instructions in the generated code.
  • (Syntax-directed) translation schemes. A translation scheme is a notation for attaching program fragments to the production of a grammar.

No comments:

Post a Comment