Compiler/Verifying syntax

Compiler/Verifying syntax is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Verifying Syntax
A Syntax Analyzer that verifies a token stream,
outputs a string "true" if the token stream matches the grammar requirement,
outputs a string "false" if the token stream does not match the grammar.

Task
The program reads input from a file of token stream,
reads it and outputs a string "true" if the token stream matches the grammar,
outputs a string "false" and error messages if the token stream does not match the grammar,
based on the grammar below. The grammar is written in Extended Backus-Naur Form (EBNF).

Grammar

stmt         =         expr ; 

expr         =         expr_level_2; 
expr_level_2 =         expr_level_3 {"or" expr_level_3} ; 
expr_level_3 =         expr_level_4 {"and" expr_level_4} ; 
expr_level_4 = ["not"] expr_level_5 [('=' | '<') expr_level_5] ; 
expr_level_5 =         expr_level_6 {('+' | '-') expr_level_6} ; 
expr_level_6 =         primary      {('*' | '/') primary} ; 

primary      =         Identifier
                     | Integer
                     | '(' expr ')'
                     | "true"
                     | "false"
                     ;
Integer      =         Digit {Digit};

Identifier   =         Letter {Letter | Digit | '_'};

Digit        =         "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Letter       =         "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" 
                     | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" 
                     | "u" | "v" | "w" | "x" | "y" | "z" | "A" | "B" | "C" | "D" 
                     | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" 
                     | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" 
                     | "Y" | "Z" ;

Julia

<lang julia>function substituteinnerparentheses(s, subs)

   ((i = findlast('(', s)) == nothing) && return (s, false)
   ((j = findfirst(')', s[i:end])) == nothing) && return (s, false)
   okparse(s[i+1:j+i-2]) || return (s, false)
   return s[1:i-1] * " " * subs * " " * s[j+i:end], true

end

function okparse(s)

   while findfirst('(', s) != nothing
       s, okinparentheses = substituteinnerparentheses(s, "true")
       okinparentheses || return false
   end
   s = strip(s)
   if occursin(r"(and|or|[\=\<\+\-\*\/])\s*(and|or|[\=\<\+\-\*\/])", s) ||
       occursin(r"(^(and|^or|^[\=\<\+\-\*\/]))|((and|or|[\=\<\+\-\*\/])$)", s)
       return false
   end
   for item in split(s, r"\s+")
       !occursin(
           r"^[a-zA-Z][a-zA-Z_0-9]*$|^\d+$|^true$|^false$|^or$|^and$|^not$|^\=$|^\<$|^\+$|^-$|^\*$|^\/$",
           item) && return false
   end
   s = replace(replace(replace(s, "and" => "&&"), "or" => "||"), "not" => "!")
   try 
       Meta.parse(s)
   catch
       return false
   end
   return true

end

teststatements = [ " not 3 < 4 or (true or 3 / 4 + 8 * 5 - 5 * 2 < 56) and 4 * 3 < 12 or not true", " and 3 < 2", "not 7 < 2", "4 * (32 - 16) + 9 = 73", "235 76 + 1" ]

for s in teststatements

   println("The compiler parses the statement { $s } and outputs: ", okparse(s))

end

</lang>

Output:

The compiler parses the statement {  not 3 < 4 or (true or 3 /  4 + 8 *  5 - 5 * 2 < 56) and 4 * 3  < 12 or not true } and outputs: true
The compiler parses the statement {  and 3 < 2 } and outputs: false
The compiler parses the statement { not 7 < 2 } and outputs: true
The compiler parses the statement { 4 * (32 - 16) + 9 = 73 } and outputs: true
The compiler parses the statement { 235 76 + 1 } and outputs: false