Skip to content
Yet another compiler generator
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
css
docs
img
js
template
README.md
index.html

README.md

Introduction

This project is base on https://github.com/zaach/jison. I start from my own catpreter when I realized that LL can't parse CMM language, then I came across jison for help. Through out reading jison's source file, I learn more about compiler and I was amazed about the power of BNF. The most interested part of jison is it use BNF to define BNF. As the author told me, bootstraping is wonderful!

Dependencies

  • catjs
  • jison
  • jquery
  • jquery ui
  • jade
  • seajs
  • bootstrap
  • codemirror

Issue

  • unable to dectect error address, only throw error outside
  • type varify is not supported

Feature

EBNF

? 0-1
* 0-*
+ 1-*
| optional

Virsual machine spec

Assembly instruction

Following define a stack-oriented instruction set. Stack-oriented defined instruction set differ from register-oriented instruction set in that it's instruction set use stack rather than registers for operation.

def   define variable
ld    load varible value into stack top
st    store stack top into varible
add   add top two element in stack,store result in accumulator
sub   sub top two element in stack,store result in accumulator
mul   multiple top two element in stack,store result in accumulator
div   divide top two element in stack,store result in accumulator
eq    test if top two element in stack are equal
neq   test if top two element in stack are not equal
lt    test if top element is little then under element in stack
ja    change program count in all condition
jt    change program count if stack top is truly value
jf    change program count if stack top is falsy value
push  push value in stack
pop   pop stack top
read  standard input
write standard output
label define label stand for address
halt  end of program

Registers

  • sp: stack pointer
  • pc: program count
  • ac: accumulator(deprecated)

Brief introdution

Virtual machine code definition.

function Machine () {
  this.stack = []; // memory stack
  this.registers = {sp: 0, pc: 0, ac: 0};
  this.memory = []; // memory used to store instructions
  this.symbols = {};
  this.buffer = ''; // output buffer, could be seen as terminal or anything you like
};

Stack operation.

Let's examine how Assembler works. We just explain the simplest part here, say we want to calculate 1 + 2 and write it in output. CMM compiler which create by Catpreter will do the work for us to create assembles so we don't need to afraid of lex, grammar analysis. Result assembles will be:

push 1
push 2
add
write
halt

Now let's take a look at these instructions to understack stack-oriented instruction-set.

 -------
|       | 
|-------|
|       |
|-------|
|       | <-- stack top
 -------

push 1

 -------
|       | 
|-------|
|       | <-- stack top
|-------|
|   1   |
 -------

push 2

 -------
|       | <-- stack top
|-------|
|   2   | 
|-------|
|   1   |
 -------

add

 -------                   -------                     -------                     -------               
|       | <-- stack top   |       |                   |       |                   |       |              
|-------|                 |-------|                   |-------|                   |-------|              
|   2   |                 |       | <-- stack top     |       |                   |       |   <-- stack top
|-------|                 |-------|                   |-------|                   |-------|              
|   1   |                 |   1   |                   |       |  <-- stack top    |   3   |             
 -------                   -------                     -------                     -------               

write

 -------
|       | 
|-------|
|       |
|-------|
|       | <-- stack top
 -------

After all, we will get the result we want 3

On the contrary, follow is what register-oriend instruction-set's behaviour:

 -------
|       | <-- accumulator
 -------

 -------
|       | <-- stack top 
|-------|
|   1   |
|-------|
|   2   |
 -------

ld

 -------
|   1   | <-- accumulator
 -------

 -------
|       | 
|-------|
|       | <-- stack top 
|-------|
|   2   |
 -------

add

 -------
|   3   | <-- accumulator
 -------

 -------
|       | 
|-------|
|       | 
|-------|
|       | <-- stack top
 -------

st

 -------
|       | <-- accumulator
 -------

 -------
|       | 
|-------|
|       | <-- stack top 
|-------|
|   3   |
 -------

I don't want to take a close look at why there are two approch and what's the difference and EVEN which is better, if you are interested, I recommand you to read this book 汇编语言与计算机体系结构,使用c++和Java. I benefit a lot from this book.

Catpreter spec

BNF defined grammar

prog
  : statement
  ;
statement
  : compound_statement
  | expression_statement
  | selection_statement
  | iteration_statement
  | declaration
  ;
compound_statement
  : '{' '}'
  | '{' statement_list '}'
  ;
statement_list
  : ( statement )+
  ;
expression_statement
  : ';'
  | expression ';'
  ;
selection_statement
  : 'if' '(' expression ')' statement ( 'else' statement )?
  ;
iteration_statement
  : 'while' '(' expression ')' statement
  ;
expression
  : assignment_expression ( ',' assignment_expression )*
  ;
constant_expression
  : equality_expression
  ;
assignment_expression
  : equality_expression
  | primary_expression assignment_operator assignment_expression
  ;
equality_expression
  : relational_expression ( '==' relational_expression | '<>' relational_expression )*
  ;
relational_expression
  : additive_expression ( '<' additive_expression )*
  ;
additive_expression
  : multiplicative_expression ( '+' multiplicative_expression | '-' multiplicative_expression )*
  ;
multiplicative_expression
  : unary_expression ( '*' unary_expression | '/' unary_expression )*
  ;
unary_expression
  : postfix_expression
  | unary_operator unary_expression
  ;
postfix_expression
  : primary_expression ( '[' expression ']' )*
  ;
primary_expression
  : constant
  | IDENTIFIER
  | '(' expression ')'
  ;
declaration
  : declarator_specifiers init_declarator_list ';'
  ;
declarator_specifiers
  : 'int'
  | 'real'
  ;
init_declarator_list
  : init_declarator ( ',' init_declarator )*
  ;
init_declarator
  : declarator ( '=' initializer )?
  ;
declarator
  : IDENTIFIER ( '[' ( constant_expression )? ']' )*
  ;
initializer
  : assignment_expression
  ;
constant
  : INT_LITERAL
  | REAL_LITERAL
  ;
assignment_operator
  : '='
  ;
unary_operator
  : '+'
  | '-'
  | 'read'
  | 'write'
  ;

After grammar generator:

// This file was generated automatically by genGrammar.js
// Don't edit it directly
var grammar = { prog: [ [ 'statement' ] ],
  statement: 
   [ [ 'compound_statement' ],
     [ 'expression_statement' ],
     [ 'selection_statement' ],
     [ 'iteration_statement' ],
     [ 'declaration' ] ],
  compound_statement: [ [ '\'{\'', '\'}\'' ], [ '\'{\'', 'statement_list', '\'}\'' ] ],
  statement_list: [ [ { '+': [ 'statement' ] } ] ],
  expression_statement: [ [ '\';\'' ], [ 'expression', '\';\'' ] ],
  selection_statement: 
   [ [ '\'if\'',
       '\'(\'',
       'expression',
       '\')\'',
       'statement',
       { '?': [ '\'else\'', 'statement' ] } ] ],
  iteration_statement: [ [ '\'while\'', '\'(\'', 'expression', '\')\'', 'statement' ] ],
  expression: 
   [ [ 'assignment_expression',
       { '*': [ '\',\'', 'assignment_expression' ] } ] ],
  constant_expression: [ [ 'equality_expression' ] ],
  assignment_expression: 
   [ [ 'equality_expression' ],
     [ 'primary_expression',
       'assignment_operator',
       'assignment_expression' ] ],
  equality_expression: 
   [ [ 'relational_expression',
       { '*': 
          [ { '|': 
               [ [ '\'==\'', 'relational_expression' ],
                 [ '\'<>\'', 'relational_expression' ] ] } ] } ] ],
  relational_expression: 
   [ [ 'additive_expression',
       { '*': [ '\'<\'', 'additive_expression' ] } ] ],
  additive_expression: 
   [ [ 'multiplicative_expression',
       { '*': 
          [ { '|': 
               [ [ '\'+\'', 'multiplicative_expression' ],
                 [ '\'-\'', 'multiplicative_expression' ] ] } ] } ] ],
  multiplicative_expression: 
   [ [ 'unary_expression',
       { '*': 
          [ { '|': 
               [ [ '\'*\'', 'unary_expression' ],
                 [ '\'/\'', 'unary_expression' ] ] } ] } ] ],
  unary_expression: 
   [ [ 'postfix_expression' ],
     [ 'unary_operator', 'unary_expression' ] ],
  postfix_expression: 
   [ [ 'primary_expression',
       { '*': [ '\'[\'', 'expression', '\']\'' ] } ] ],
  primary_expression: 
   [ [ 'constant' ],
     [ 'IDENTIFIER' ],
     [ '\'(\'', 'expression', '\')\'' ] ],
  declaration: [ [ 'declarator_specifiers', 'init_declarator_list', '\';\'' ] ],
  declarator_specifiers: [ [ '\'int\'' ], [ '\'real\'' ] ],
  init_declarator_list: [ [ 'init_declarator', { '*': [ '\',\'', 'init_declarator' ] } ] ],
  init_declarator: [ [ 'declarator', { '?': [ '\'=\'', 'initializer' ] } ] ],
  declarator: 
   [ [ 'IDENTIFIER',
       { '*': [ '\'[\'', { '?': [ 'constant_expression' ] }, '\']\'' ] } ] ],
  initializer: [ [ 'assignment_expression' ] ],
  constant: [ [ 'INT_LITERAL' ], [ 'REAL_LITERAL' ] ],
  assignment_operator: [ [ '\'=\'' ] ],
  unary_operator: [ [ '\'+\'' ], [ '\'-\'' ], [ '\'read\'' ], [ '\'write\'' ] ] };
try{exports.grammar = grammar;}catch(err){}

After eliminate left recursive, extract common factor and expand EBNF ? * +:

{ prog: [ [ 'statement' ] ],
  statement: 
   [ [ 'compound_statement' ],
     [ 'expression_statement' ],
     [ 'selection_statement' ],
     [ 'iteration_statement' ],
     [ 'declaration' ] ],
  compound_statement: [ [ '\'{\'', 'compound_statement$c_cJFmBc' ] ],
  statement_list: [ [ 'statement_list$+' ] ],
  expression_statement: [ [ '\';\'' ], [ 'expression', '\';\'' ] ],
  selection_statement: 
   [ [ '\'if\'',
       '\'(\'',
       'expression',
       '\')\'',
       'statement',
       'selection_statement$?' ] ],
  iteration_statement: [ [ '\'while\'', '\'(\'', 'expression', '\')\'', 'statement' ] ],
  expression: [ [ 'assignment_expression', 'expression$*' ] ],
  constant_expression: [ [ 'equality_expression' ] ],
  assignment_expression: 
   [ [ 'equality_expression' ],
     [ 'primary_expression',
       'assignment_operator',
       'assignment_expression' ] ],
  equality_expression: [ [ 'relational_expression', 'equality_expression$*' ] ],
  relational_expression: [ [ 'additive_expression', 'relational_expression$*' ] ],
  additive_expression: [ [ 'multiplicative_expression', 'additive_expression$*' ] ],
  multiplicative_expression: [ [ 'unary_expression', 'multiplicative_expression$*' ] ],
  unary_expression: 
   [ [ 'postfix_expression' ],
     [ 'unary_operator', 'unary_expression' ] ],
  postfix_expression: [ [ 'primary_expression', 'postfix_expression$*' ] ],
  primary_expression: 
   [ [ 'constant' ],
     [ 'IDENTIFIER' ],
     [ '\'(\'', 'expression', '\')\'' ] ],
  declaration: [ [ 'declarator_specifiers', 'init_declarator_list', '\';\'' ] ],
  declarator_specifiers: [ [ '\'int\'' ], [ '\'real\'' ] ],
  init_declarator_list: [ [ 'init_declarator', 'init_declarator_list$*' ] ],
  init_declarator: [ [ 'declarator', 'init_declarator$?' ] ],
  declarator: [ [ 'IDENTIFIER', 'declarator$*' ] ],
  initializer: [ [ 'assignment_expression' ] ],
  constant: [ [ 'INT_LITERAL' ], [ 'REAL_LITERAL' ] ],
  assignment_operator: [ [ '\'=\'' ] ],
  unary_operator: [ [ '\'+\'' ], [ '\'-\'' ], [ '\'read\'' ], [ '\'write\'' ] ],
  'statement_list$+': [ [ 'statement', 'statement_list$+$*' ] ],
  'statement_list$+$*': [ [ 'statement', 'statement_list$+$*' ], [] ],
  'selection_statement$?': [ [ '\'else\'', 'statement' ], [] ],
  'expression$*': [ [ '\',\'', 'assignment_expression', 'expression$*' ], [] ],
  'equality_expression$*': 
   [ [ 'equality_expression$*$|_pynGFz', 'equality_expression$*' ],
     [] ],
  'equality_expression$*$|_pynGFz': 
   [ [ '\'==\'', 'relational_expression' ],
     [ '\'<>\'', 'relational_expression' ] ],
  'relational_expression$*': 
   [ [ '\'<\'', 'additive_expression', 'relational_expression$*' ],
     [] ],
  'additive_expression$*': 
   [ [ 'additive_expression$*$|_CuSWdJ', 'additive_expression$*' ],
     [] ],
  'additive_expression$*$|_CuSWdJ': 
   [ [ '\'+\'', 'multiplicative_expression' ],
     [ '\'-\'', 'multiplicative_expression' ] ],
  'multiplicative_expression$*': 
   [ [ 'multiplicative_expression$*$|_FhAVbz',
       'multiplicative_expression$*' ],
     [] ],
  'multiplicative_expression$*$|_FhAVbz': 
   [ [ '\'*\'', 'unary_expression' ],
     [ '\'/\'', 'unary_expression' ] ],
  'postfix_expression$*': 
   [ [ '\'[\'', 'expression', '\']\'', 'postfix_expression$*' ],
     [] ],
  'init_declarator_list$*': [ [ '\',\'', 'init_declarator', 'init_declarator_list$*' ], [] ],
  'init_declarator$?': [ [ '\'=\'', 'initializer' ], [] ],
  'declarator$*': [ [ '\'[\'', 'declarator$*$?', '\']\'', 'declarator$*' ], [] ],
  'declarator$*$?': [ [ 'constant_expression' ], [] ],
  'compound_statement$c_cJFmBc': [ [ '\'}\'' ], [ 'statement_list', '\'}\'' ] ] }

Conclusion

Eliminate left recursive

compound_statement
  : '{' '}'
  | '{' statement_list '}'
  ;

  compound_statement: [ 
    [ '\'{\'', '\'}\'' ],
    [ '\'{\'', 'statement_list', '\'}\'' ] 
  ],

  compound_statement: [ [ '\'{\'', 'compound_statement$c_cJFmBc' ] ],
  'compound_statement$c_cJFmBc': [ [ '\'}\'' ], [ 'statement_list', '\'}\'' ] ] }

eg:

 compund_statement
  : '{' compound_statement$c_cJFmBc
  ;
 compound_statement$c_cJFmBc
  : 'statement_list' '}'
  | '}'
  ;

Extend EBNF

expression
  : assignment_expression ( ',' assignment_expression )*
  ;

expression: [[
 'assignment_expression',
  { '*': [ '\',\'', 'assignment_expression' ] } 
 ]]


 expression: [ [
   'assignment_expression', 'expression$*' 
 ] ],
 'expression$*': [ ['\',\'', 'assignment_expression', 'expression$*' ], [] ],

eg:

expression
  : assignment_expression expression$* 
  ;
 expression$*
  : ',' assignment_expression expression$*
  | ϵ
  ;

Next up

FIRST

FOLLOW

Closure

Translation table

CMM

Lex

DIGIT                     \d+
INT                       {DIGIT}+ 
REAL                      {INT}\.{INT}('e'[-+]?{INT})?
LETTER                    [a-zA-Z]
NUMBER                    [0-9]
IDENTIFIER                {LETTER}({LETTER}|{NUMBER}|'_')*

"//".*                  /* ignore line comment */
"/*"                    {this.begin('comment');}
<comment>"*/"           {this.popState();}
<comment>.              {/* skip comment content*/}
\s+                     /* ignore white space */
"if"                    return 'if';
"else"                  return 'else';
"while"                 return 'while';
"read"                  return 'read';
"write"                 return 'write';
"int"                   return 'int';
"real"                  return 'real';
{REAL}                  return 'REAL_LITERAL';
{INT}                   return 'INT_LITERAL';
{IDENTIFIER}            return 'IDENTIFIER';
"+="                    return '+=';
"-="                    return '-=';
"*="                    return '*=';
"/="                    return '/=';
"=="                    return '==';
"<>"                    return '<>';
"+"                     return '+';
"-"                     return '-';
"*"                     return '*';
"/"                     return '/';
"<"                     return '<';
"["                     return '[';
"]"                     return ']';
"="                     return '=';
"("                     return '(';
")"                     return ')';
";"                     return ';';
"{"                     return '{';
"}"                     return '}';
","                     return ',';
.                       /* ignore */

Grammar

%start prog
prog
  : statement_list EOF
  ;
statement_list
  : statement
  | statement_list statement
  ;
statement
  : compound_statement
  | expression_statement
  | selection_statement
  | iteration_statement
  | declaration
  ;

compound_statement
  : empty_compound_statement
  | wrapped_compound_statement
  ;
empty_compound_statement
  : '{' '}'
  ;
wrapped_compound_statement
  : '{' statement_list '}'
  ;

selection_statement
  : if_statement
  | if_else_statement
  ;
if_statement
  : 'if' '(' expression ')' statement
  ;
if_else_statement
  : 'if' '(' expression ')' statement 'else' statement
  ;

iteration_statement
  : 'while' '(' expression ')' statement
  ;

expression_statement
  : empty_expression_statement
  | ended_expression_statement
  | write_expression_statement
  | read_expression_statement
  ;
empty_expression_statement
  : ';'
  ;
ended_expression_statement
  : expression ';'
  ;
write_expression_statement
  : 'write' expression ';'
  ;
read_expression_statement
  : 'read' IDENTIFIER
  ;

expression
  : assignment_expression
  | expression ',' assignment_expression
  ;
assignment_expression
  : equality_expression
  | postfix_expression assignment_operator assignment_expression
  ;
assignment_operator
  : '='
  | '+='
  | '-='
  | '*='
  | '/='
  ;
equality_expression
  : relational_expression
  | equality_expression equality_operator relational_expression
  ;
equality_operator
  : '=='
  | '<>'
  ;
relational_expression
  : additive_expression
  | relational_expression '<' additive_expression
  ;
additive_expression
  : multiplicative_expression
  | additive_expression '+' multiplicative_expression
  | additive_expression '-' multiplicative_expression
  ;
multiplicative_expression
  : unary_expression
  | multiplicative_expression '*' unary_expression
  | multiplicative_expression '/' unary_expression
  ;
unary_expression
  : postfix_expression
  | '+' unary_expression
  | minus_unary_expression
  ;
minus_unary_expression
  : '-' unary_expression
  ;
postfix_expression
  : primary_expression
  | primary_expression '[' INT_LITERAL ']'
  ;
primary_expression
  : INT_LITERAL
  | REAL_LITERAL
  | IDENTIFIER
  | '(' expression ')'
  ;

declaration
  : declarator_specifiers init_declarator_list ';'
  ;
declarator_specifiers
  : 'int'
  | 'real'
  ;
init_declarator_list
  : init_declarator
  | init_declarator_list ',' init_declarator
  ;
init_declarator
  : declarator
  | declarator '=' initializer
  ;
declarator
  : IDENTIFIER
  | declarator '[' INT_LITERAL ']'
  ;
initializer
  : assignment_expression
  ;
You can’t perform that action at this time.