Parsing expression grammar (PEG)

Parsing expression grammar or PEG is a type of analytic formal grammar. It was first proposed by Bryan Ford in 2004. It is related to the top-down parsing model.

It looks similar to CFG, but different in that it uses "/" instead of "|" to specify the derivation choices of a non-terminal. In doing so it also specifies that the rules delimited by "/" are chosen in the order of appearance. This in effect adds a priority order to the rules involved, and avoids relevant ambiguity. Say in a CFG state you have two rules in shift/reduce or reduce/reduce conflict, which in CFG needs extra priority/precedence specification, now in PEG one just choose the one with high priority. This way it claims that: unlike CFG, PEG cannot be ambiguous.

Any PEG can be parsed in linear time by using a packrat parser.

Advantages of PEG include: no ambiguity; more powerful than regular expressions (this does not sound a very special advantage though, since LL/LR are also more powerful than regular expressions); does not need a separate tokenization step (such as by lex), tokenization rules in PEG can be written the same way as other grammar rules.

Disadvantages of PEG include: large memory consumption; cannot use left-recursion (same as LL); may contain subtle grammar errors and the author needs to tweak the grammar a bit; cannot recognize some unambiguous non-deterministic grammars, for example: S ← 'x' S 'x' | 'x'. Note that LL and LR also cannot recognize this, but CYK algorithm can.

Reference:
[1] http://en.wikipedia.org/wiki/Parsing_expression_grammar

CSE 231 - Advanced Compiler Design and Implementation

CSE 231 - Advanced Compiler Design and Implementation.

Pay attention to the link "List of Papers for Presentations". These are papers from the most prestigeous conferences on compiler up to 2002.

Linkers and Loaders

== Linkers and Loaders ==
By John R. Levine. 2000. ISBN 1-55860-496-0

- linkers and loaders are part of the software toolkit for almost 
  as long as there have been computers.
- This book is for: 
  students, programmers, computer language designers and developers.
- All the linker writers in the world could probably fit in one room, 
  and half of them would already have this book because they reviewed 
  the manuscript.

Chapter 1. Linking and Loading

1.1 What do linkers and loaders do?
- Basic job of linker/loader: binds more abstract names to more 
  concrete names. (name management, address binding)

1.2 Address binding: A historical perspective
- Linker and Loader divides the job: Linker do part of address binding, 
  assign relative addresses. Loader do final step of assigning actual addresses.

1.3 Linking and Loading
- linker does 1) symbol resolution, loader does 2) program loading. 
  Either can do 3) relocation.
- There are linking loaders that do all 3 functions
- Both patch object code

- Two-pass linking: linking is fundamentally a 2-pass process: 
  step 1) collecting info, step 2) linking
  object files + shared lib + normal lib + linker control files + cmd line args --> 
  (linker) --> 
  Debug symbol file + Executable file + link/load map
- Object code libraries
- Relocation and code modification

1.4 Compiler drivers
- assembly code --> object code --> link object code and library together
- Linker command languages. Ways of passing commands to a linker:
  1) command line, 2) intermixed with obj files, 
  3) embedded in obj files, 4) separate config language.

1.5 Linking: A true-life example

Chapter 2. Architecture issues

- Architecture: 1) hardward (program addressing, instruction formats), 2) OS.

2.1 ABI (Application Binary Interfaces)
- procedure call etc.

2.2 Memory addresses
- Byte order & alignment
  IBM/Motorola: big endian
  Intel/DEC: little endian
- misalignment: fault, or loss of performance
- register. size: program address

2.3 Address formation
- clean: 360/370/390 
- simple: SPARC (RISC): v8 (32-bit), v9 (64-bit)
  similar to other RISC arch: MIPS, Alpha
- irregular: x86

2.4 Instruction formats
- opcode operand
- direct/register addressing, base/indexed addressing
- fixed/variable length instruction
  SPARC: all 4 bytes
  370: 2/4/6 bytes
  x86: 1-14 bytes

2.5 Procedure calls and addressibility
- abandon direct addressing for shorter instructions at the cost of 
  more complicated programming.
- bootstrapping for non-direct addressing
- procedure calls
- stack frame
  arguments/local variables - on stack
  local/global static variables - on heap

Programming language for Multi-core computers

Intel Develops Programming Language For Multi-Core Computers