Parser_combinators_for_syntax_errors_searching

The research of applcation of parser combinators for error searching in the code.

Abstract

Parser-combinators is a popular approach to parsing of sequences generated by context-free grammars, which can be specialized data formats (e.g. JSON, YAML), markup languages like XML of HTML. At the same time, this approach is rarely used for parsing programming languages.

The purpose of this research is to study the application of parser-combinators for programming languages processing, and more precisely for searching of syntax errors. The method that had been developed during this research was compared with an algorithm of syntax analysis of programming languages using parser-generators. Parser-combinator takes less time on average to find a syntax error in the source code. Its average time complexity is O(n), where n is the length of the input sequence, while parser-generator has an average O(n²) complexity. Moreover, a parser-combinator requires less memory than a parser-generator.

Usage

You can find the examples of programmes in examples directory. In order to execute script you should choose mode (CF or CS: context free an context sensitive respectively) of execution as a first argument and path to the executable file as the second one. Example is below:

git clone https://github.com/mmkuznecov/CF_and_CS_grammars_comparsion
cd CF_and_CS_grammars_comparsion/src
python3 main.py -m CF -f ../bubble_sort.rlang

Features

Language currently supporting:

• Math (+ - * / %), logical and bitwise operations

• Variables of different types (int, float, string, list, dict)

• If statements

• While and for loops

• Functions

The info will be updated along with adding the new functionality.

Language syntax

Firstly, all statements end with colon

Comment section starts with double slash:

// comment example

Output section provided with print keyword:

print("Hello world!")

Variables are defined with the let keyword:

let a: int;
let b = 10;

You can assign value along with variable declaration as you can see above.

Language provides working with math, logical and bitwise operations:

let a = 10 * 2 + 3; // value of a is 23 because there is a precedence of operations
let b = true or false; // value of b is true
let c = 1 & 0; // value of c is 0

Next main constructions will be described with the examples:

If statement example:

let a = 10;
if a > 5{
    print("var is greater than 5");
}
else {
    print("var is less than 5"); 
}

// first statement will be printed

For loop example:

let break = false; // just a var
let i: int;

for i = 0; i < 10 and !break; ++i {
  if i % 2 == 0 or i < 2 {
    print(i);
  }
  if i > 4 
    break = true;
}

// following programm will print numbers 0 1 2 4

While loop example:

let i = 1;

while i <= 10{
    print(i);
    i+=1;
}

// programm will print numbers from 1 to 10

Function example:

let x = 2;
let y = 3;

fn add_numbers (a: int, b: int){
    return a + b;
}

print(add_numbers(x,y));

// 5 will be printed

Also language supports function composition. You can find the example of recursion in factorial_recursion.rlang file in examples directory.

In order to check all keywords and constructions, you can look at the code of lexer and parser at src directory.