Compiler/Verifying syntax: Difference between revisions
m (→{{header|Go}}: Corrected typo.) |
No edit summary |
||
Line 219:
The compiler parses the statement { 4 * (32 - 16) + 9 = 73 } and outputs: true
The compiler parses the statement { 235 76 + 1 } and outputs: false
</pre>
=={{header|Perl}}==
<lang>#!/usr/bin/perl
use strict;
use warnings;
sub error { die s/\G/{{\U@_}}/r }
sub want { /\G\Q$_[0]/gc ? pop : error $_[1]; 1 }
sub expr
{
my $level = shift;
/\G\h+/gc;
/\G(true|false)\b/gc or
/\G\(/gc && want ')', "expected a closing paren", expr(0) or
/\G(?=(and|or)\b)/gc && error "expected a primary, '$1' is an operator" or
/\Gnot\b/gc && expr(5) or
/\G(?:\d+|[a-zA-Z]\w*)/gc or
error "expected a primary";
/\G\h+/gc ? 1 :
$level <= 2 && /\Gor\b/gc ? expr(2) :
$level <= 3 && /\Gand\b/gc ? expr(4) :
$level <= 4 && /\G[=<]/gc ? expr(4.5) :
$level == 4.5 && /\G(?=[=<])/gc ? error "operator is non-associative" :
$level <= 5 && /\G[+-]/gc ? expr(6) :
$level <= 6 && /\G[*\/]/gc ? expr(7) :
return 1 while 1;
}
while( <DATA> )
{
print eval { want "\n", "expected end of input", expr(0) } ?
"${_}true\n" : "$@false\n", "\n";
}
__DATA__
(42 + 3
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
2 < 3 < 4
4 * (32 - 16) + 9 = 73
235 76 + 1
a + b = not c and false
ab_c / bd2 or < e_f7
g not = h
été = false
i++
j & k
l or _m</lang>
{{out}}
<pre>
(42 + 3{{EXPECTED A CLOSING PAREN}}
false
not 3 < 4 or (true or 3 / 4 + 8 * 5 - 5 * 2 < 56) and 4 * 3 < 12 or not true
true
{{EXPECTED A PRIMARY, 'AND' IS AN OPERATOR}}and 3 < 2
false
not 7 < 2
true
2 < 3 {{OPERATOR IS NON-ASSOCIATIVE}}< 4
false
4 * (32 - 16) + 9 = 73
true
235 {{EXPECTED END OF INPUT}}76 + 1
false
a + b = not c and false
true
ab_c / bd2 or {{EXPECTED A PRIMARY}}< e_f7
false
g {{EXPECTED END OF INPUT}}not = h
false
{{EXPECTED A PRIMARY}}été = false
false
i+{{EXPECTED A PRIMARY}}+
false
j {{EXPECTED END OF INPUT}}& k
false
l or {{EXPECTED A PRIMARY}}_m
false
</pre>
|
Revision as of 17:46, 27 December 2019
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" ;
Go
If "and", "or", "not" and "=" are replaced by the corresponding symbols: "&&", "||", "!" and "==", then the task grammar is a subset of Go's own grammar - operator precedence and identifier construction are the same.
After making the appropriate substitutions, we can therefore use the parser in Go's standard library to verify whether the statements are valid or not. As expressions cannot be statements in Go, we simply parse the latter as expressions.
However, before applying the parser, we first need to ensure that the expressions don't include any characters (including non-ASCII) or usages thereof which Go would otherwise permit. Note that it's not necessary to specifically check for '++' and '--' as these are statements in Go and can't appear in expressions anyway. <lang go>package main
import (
"fmt" "go/parser" "regexp" "strings"
)
var (
re1 = regexp.MustCompile(`[^_a-zA-Z0-9\+\-\*/=<\(\) ]`) re2 = regexp.MustCompile(`\b_\w*\b`)
)
var subs = [][2]string{
{"=", "=="}, {" not ==", " !="}, {" not <", " >="}, {" not ", " ! "}, {" or ", " || "}, {" and ", " && "},
}
func possiblyValid(expr string) error {
matches := re1.FindStringSubmatch(expr) if matches != nil { return fmt.Errorf("invalid character %q found", []rune(matches[0])[0]) } if re2.MatchString(expr) { return fmt.Errorf("identifier cannot begin with an underscore") } return nil
}
func modify(err error) string {
e := err.Error() for _, sub := range subs { e = strings.ReplaceAll(e, strings.TrimSpace(sub[1]), strings.TrimSpace(sub[0])) } return strings.Split(e, ":")[2][1:] // remove location info as may be inaccurate
}
func main() {
exprs := []string{ " 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", "a + b = not c and false", "ab_c / bd2 or < e_f7", "g not = h", "été = false", "i++", "j & k", "l or _m", }
for _, expr := range exprs { fmt.Printf("Statement to verify: %q\n", expr) if err := possiblyValid(expr); err != nil { fmt.Printf("\"false\" -> %s\n\n", err.Error()) continue } expr = fmt.Sprintf(" %s ", expr) // make sure there are spaces at both ends for _, sub := range subs { expr = strings.ReplaceAll(expr, sub[0], sub[1]) } _, err := parser.ParseExpr(expr) if err != nil { fmt.Println(`"false" ->`, modify(err)) } else { fmt.Println(`"true"`) } fmt.Println() }
}</lang>
- Output:
Statement to verify: " not 3 < 4 or (true or 3 / 4 + 8 * 5 - 5 * 2 < 56) and 4 * 3 < 12 or not true" "true" Statement to verify: " and 3 < 2" "false" -> expected operand, found 'and' Statement to verify: "not 7 < 2" "true" Statement to verify: "4 * (32 - 16) + 9 = 73" "true" Statement to verify: "235 76 + 1" "false" -> expected 'EOF', found 76 Statement to verify: "a + b = not c and false" "true" Statement to verify: "ab_c / bd2 or < e_f7" "false" -> expected operand, found '<' Statement to verify: "g not = h" "true" Statement to verify: "été = false" "false" -> invalid character 'é' found Statement to verify: "i++" "false" -> expected 'EOF', found '++' Statement to verify: "j & k" "false" -> invalid character '&' found Statement to verify: "l or _m" "false" -> identifier cannot begin with an underscore
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) # Julia allows expressions like 2 + + + 3 but these are not allowed here if occursin(r"(and|or|[\=\<\+\-\*\/])\s*(and|or|[\=\<\+\-\*\/])", s) || occursin(r"(^(and|^or|^[\=\<\+\-\*\/]))|((and|or|[\=\<\+\-\*\/])$)", s) return false end # Julia allows ., ,, ; and operators like % but these are not allowed here # permitted: -+*/ true false and or not, ascii identifiers, and integers 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 # change and, or, and not to the corresponding Julia operators s = replace(replace(replace(s, "and" => "&&"), "or" => "||"), "not" => "!") try # Use Julia's parser, which will throw exception if it parses an error 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
Perl
<lang>#!/usr/bin/perl
use strict; use warnings;
sub error { die s/\G/Template:\U@/r } sub want { /\G\Q$_[0]/gc ? pop : error $_[1]; 1 }
sub expr
{ my $level = shift; /\G\h+/gc; /\G(true|false)\b/gc or /\G\(/gc && want ')', "expected a closing paren", expr(0) or /\G(?=(and|or)\b)/gc && error "expected a primary, '$1' is an operator" or /\Gnot\b/gc && expr(5) or /\G(?:\d+|[a-zA-Z]\w*)/gc or error "expected a primary"; /\G\h+/gc ? 1 : $level <= 2 && /\Gor\b/gc ? expr(2) : $level <= 3 && /\Gand\b/gc ? expr(4) : $level <= 4 && /\G[=<]/gc ? expr(4.5) : $level == 4.5 && /\G(?=[=<])/gc ? error "operator is non-associative" : $level <= 5 && /\G[+-]/gc ? expr(6) : $level <= 6 && /\G[*\/]/gc ? expr(7) : return 1 while 1; }
while( )
{ print eval { want "\n", "expected end of input", expr(0) } ? "${_}true\n" : "$@false\n", "\n"; }
__DATA__ (42 + 3 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 2 < 3 < 4 4 * (32 - 16) + 9 = 73 235 76 + 1 a + b = not c and false ab_c / bd2 or < e_f7 g not = h été = false i++ j & k l or _m</lang>
- Output:
(42 + 3{{EXPECTED A CLOSING PAREN}} false not 3 < 4 or (true or 3 / 4 + 8 * 5 - 5 * 2 < 56) and 4 * 3 < 12 or not true true {{EXPECTED A PRIMARY, 'AND' IS AN OPERATOR}}and 3 < 2 false not 7 < 2 true 2 < 3 {{OPERATOR IS NON-ASSOCIATIVE}}< 4 false 4 * (32 - 16) + 9 = 73 true 235 {{EXPECTED END OF INPUT}}76 + 1 false a + b = not c and false true ab_c / bd2 or {{EXPECTED A PRIMARY}}< e_f7 false g {{EXPECTED END OF INPUT}}not = h false {{EXPECTED A PRIMARY}}été = false false i+{{EXPECTED A PRIMARY}}+ false j {{EXPECTED END OF INPUT}}& k false l or {{EXPECTED A PRIMARY}}_m false