<commit_before>* Previous tutorial step - [Step 1 - Lexing](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/step1_lexing.md)

# Tutorial Step 2 - Building a Parser.


### ---> [Source Code](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/src/step2_parsing.js) for this step <---


### On code samples:
The tutorial uses ES2015+ syntax.
See examples of using Chevrotain in other [implementation languages](https://github.com/SAP/chevrotain/tree/master/examples/implementation_languages).


### Introduction:
In this tutorial we will implement a Parser for a simple SQL Select statement language
introduced in the [previous](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/step1_lexing.md) tutorial step. 

The grammar for our language:

```ANTLR
 
selectStatement
   : selectClause fromClause (whereClause)?
   
selectClause
   : "SELECT" Identifier ("," Identifier)*
   
fromClause
   : "FROM" Identifier
     
whereClause
   : "WHERE" expression
   
expression
   : atomicExpression relationalOperator atomicExpression
      
atomicExpression
   : Integer | Identifier
         
relationalOperator
   : ">" | "<"
      
```

A Chevrotain Parser analyses an [IToken](http://sap.github.io/chevrotain/documentation/0_28_0/interfaces/_chevrotain_d_.itoken.html) vector that conforms to some grammar.
The grammar is defined using the [parsing DSL](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one), which includes the following methods.

*   [CONSUME](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#consume1) - 'eat' a Token.
*   [SUBRULE](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#subrule1) - reference to another rule.
*   [OR](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#or1) - Alternation
*   [OPTION](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#option1) - optional production. 
*   [MANY](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#many1) - repetition zero or more.
*   [AT_LEAST_ONE](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one1) - repetition one or more.
*   [MANY_SEP](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#many_sep1) - repetition (zero or more) with a separator between any two items 
*   [AT_LEAST_ONE_SEP](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one_sep1) - repetition (one or more) with a separator between any two items


#### Let's implement our first grammar rule. 

```javascript
// selectStatement
//    : selectClause fromClause (whereClause)?;

const $ = this
$.RULE("selectStatement", () => {
    $.SUBRULE($.selectClause)
    $.SUBRULE($.fromClause)
    $.OPTION(() => {
        $.SUBRULE($.whereClause)        
    })
})
```

Fairly straight forward translation:
 * Non-Terminals --> SUBRULE
 * "?" --> OPTION


#### What is 'this' in this context? where do we write the grammar rules?

Each grammar rule is a property of a class that extends chevrotain.Parser.

```javascript
let allTokens = [WhiteSpace, Select, From, Where, Comma, Identifier, Integer, GreaterThan, LessThan]

class SelectParser extends chevrotain.Parser {
    /**
    * @param {IToken[]} input 
    */
    constructor(input) {
        super(input, allTokens)
        
        const $ = this;
        
        $.RULE("selectStatement", () => {
            $.SUBRULE($.selectClause)
            $.SUBRULE($.fromClause)
            $.OPTION(() => {
               $.SUBRULE($.whereClause)        
            })
        })
        
        Parser.performSelfAnalysis(this)
    }   
}
```

Important to note that:
* The **super** invocation has an array of the Tokens as the second parameter.
  This is the same array we used to define the Lexer and it is used to define the Parser's vocabulary.
* The static method **Parser.performSelfAnalysis** must be invoked at the end of the constructor.
  This is where much of the 'secret sauce' happens, including creating the inner grammar representation
  and performing static checks on the grammar.
  

#### Let's look at two more grammar rule, this time with repetition and alternation.

```javascript
// selectClause
//   : "SELECT" IDENTIFIER ("," IDENTIFIER)*;
this.selectClause =
   $.RULE("selectClause", () => {
       $.CONSUME(Select);
       $.AT_LEAST_ONE_SEP({SEP: Comma, DEF: () => {
           $.CONSUME(Identifier);
       }});
   })
 
// atomicExpression
//    : INTEGER | IDENTIFIER
this.atomicExpression =
   $.RULE("atomicExpression", () => {
       $.OR([
           {ALT: () => { $.CONSUME(Integer)}},
           {ALT: () => { $.CONSUME(Identifier)}}
       ]);
})
```


#### How can the Parser be debugged? 
The grammar rules above do not only define the grammar, they are also the code that will be run
during parsing. This means that you can debug the parser **simply by adding a break
point in the grammar**.

```javascript
// selectClause
//   : "SELECT" IDENTIFIER ("," IDENTIFIER)*;
this.selectClause =
   $.RULE("selectClause", () => {
       $.CONSUME(Select);
       // Can be debugged directly! no code generation.
       debugger;
       $.AT_LEAST_ONE_SEP({SEP: Comma, DEF: () => {
           $.CONSUME(Identifier);
       }});
   })
})
```

There **do not** exist two different representations for the grammar
and the runnable implementation (for example, grammar file vs generated code in the case of parser generators).
Again, please note that Chevrotain is **NOT** a parser generator.
Extra details cna be found [in the FAQ](https://github.com/SAP/chevrotain/blob/master/docs/faq.md#-why-should-i-use-a-parsing-dsl-instead-of-a-parser-generator).


#### But how does it work? (skip if you don't care :) )
The code above will be executed as is. Yet we have not implemented a lookahead function to
choose between the two OR alternatives ```( INTEGER | IDENTIFIER)```,
nor have we implemented logic to identify the next iteration for ```("," IDENTIFIER)*```. 
So how does it work?<commit_msg>Update step2_parsing.md<commit_after>* Previous tutorial step - [Step 1 - Lexing](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/step1_lexing.md)

# Tutorial Step 2 - Building a Parser.


### ---> [Source Code](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/src/step2_parsing.js) for this step <---


### On code samples:
The tutorial uses ES2015+ syntax.
See examples of using Chevrotain in other [implementation languages](https://github.com/SAP/chevrotain/tree/master/examples/implementation_languages).


### Introduction:
In this tutorial we will implement a Parser for a simple SQL Select statement language
introduced in the [previous](https://github.com/SAP/chevrotain/blob/master/docs/tutorial/step1_lexing.md) tutorial step. 

The grammar for our language:

```ANTLR
 
selectStatement
   : selectClause fromClause (whereClause)?
   
selectClause
   : "SELECT" Identifier ("," Identifier)*
   
fromClause
   : "FROM" Identifier
     
whereClause
   : "WHERE" expression
   
expression
   : atomicExpression relationalOperator atomicExpression
      
atomicExpression
   : Integer | Identifier
         
relationalOperator
   : ">" | "<"
      
```

A Chevrotain Parser analyses an [IToken](http://sap.github.io/chevrotain/documentation/0_28_0/interfaces/_chevrotain_d_.itoken.html) vector that conforms to some grammar.
The grammar is defined using the [parsing DSL](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one), which includes the following methods.

*   [CONSUME](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#consume1) - 'eat' a Token.
*   [SUBRULE](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#subrule1) - reference to another rule.
*   [OR](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#or1) - Alternation
*   [OPTION](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#option1) - optional production. 
*   [MANY](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#many1) - repetition zero or more.
*   [AT_LEAST_ONE](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one1) - repetition one or more.
*   [MANY_SEP](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#many_sep1) - repetition (zero or more) with a separator between any two items 
*   [AT_LEAST_ONE_SEP](http://sap.github.io/chevrotain/documentation/0_28_0/classes/_chevrotain_d_.parser.html#at_least_one_sep1) - repetition (one or more) with a separator between any two items


#### Let's implement our first grammar rule. 

```javascript
// selectStatement
//    : selectClause fromClause (whereClause)?;

const $ = this
$.RULE("selectStatement", () => {
    $.SUBRULE($.selectClause)
    $.SUBRULE($.fromClause)
    $.OPTION(() => {
        $.SUBRULE($.whereClause)        
    })
})
```

Fairly straight forward translation:
 * Non-Terminals --> SUBRULE
 * "?" --> OPTION


#### What is 'this' in this context? where do we write the grammar rules?

Each grammar rule is a property of a class that extends chevrotain.Parser.

```javascript
let allTokens = [WhiteSpace, Select, From, Where, Comma, Identifier, Integer, GreaterThan, LessThan]

class SelectParser extends chevrotain.Parser {
    /**
    * @param {IToken[]} input 
    */
    constructor(input) {
        super(input, allTokens)
        
        const $ = this;
        
        $.RULE("selectStatement", () => {
            $.SUBRULE($.selectClause)
            $.SUBRULE($.fromClause)
            $.OPTION(() => {
               $.SUBRULE($.whereClause)        
            })
        })
        
        Parser.performSelfAnalysis(this)
    }   
}
```

Important to note that:
* The **super** invocation has an array of the Tokens as the second parameter.
  This is the same array we used to define the Lexer and it is used to define the Parser's vocabulary.
* The static method **Parser.performSelfAnalysis** must be invoked at the end of the constructor.
  This is where much of the 'secret sauce' happens, including creating the inner grammar representation
  and performing static checks on the grammar.
  

#### Let's look at two more grammar rule, this time with repetition and alternation.

```javascript
// selectClause
//   : "SELECT" IDENTIFIER ("," IDENTIFIER)*;
this.selectClause =
   $.RULE("selectClause", () => {
       $.CONSUME(Select);
       $.AT_LEAST_ONE_SEP({SEP: Comma, DEF: () => {
           $.CONSUME(Identifier);
       }});
   })
 
// atomicExpression
//    : INTEGER | IDENTIFIER
this.atomicExpression =
   $.RULE("atomicExpression", () => {
       $.OR([
           {ALT: () => { $.CONSUME(Integer)}},
           {ALT: () => { $.CONSUME(Identifier)}}
       ]);
})
```


#### How can the Parser be debugged? 
The grammar rules above do not only define the grammar, they are also the code that will be run
during parsing. This means that you can debug the parser **simply by adding a break
point in the grammar**.

```javascript
// selectClause
//   : "SELECT" IDENTIFIER ("," IDENTIFIER)*;
this.selectClause =
   $.RULE("selectClause", () => {
       $.CONSUME(Select);
       // Can be debugged directly! no code generation.
       debugger;
       $.AT_LEAST_ONE_SEP({SEP: Comma, DEF: () => {
           $.CONSUME(Identifier);
       }});
   })
})
```

There **do not** exist two different representations for the grammar
and the runnable implementation (for example, grammar file vs generated code in the case of parser generators).
Again, please note that Chevrotain is **NOT** a parser generator.
Extra details can be found [in the FAQ](https://github.com/SAP/chevrotain/blob/master/docs/faq.md#-why-should-i-use-a-parsing-dsl-instead-of-a-parser-generator).


#### But how does it work? (skip if you don't care :) )
The code above will be executed as is. Yet we have not implemented a lookahead function to
choose between the two OR alternatives ```( INTEGER | IDENTIFIER)```,
nor have we implemented logic to identify the next iteration for ```("," IDENTIFIER)*```. 
So how does it work?
{'fraction_non_alphanumeric': 0.12905036894449792, 'fraction_numerical': 0.009223612447866538, 'mean_word_length': 3.5193910837259876, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 33, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3372227', 'n_tokens_mistral': 4047, 'n_tokens_neox': 3868, 'n_words': 1012}