I am writing a parser (a parser generator for PEGs) and am trying to figure out how to report errors.
Grammar:
rule: (a b)? a c ;
Input:
a d
Question: Which error message correct at position 2 for given input?
- expected "b", "c".
- expected "c".
So should it be taken into account that "b" was also expected at position?
The 1st error (expected "b", "c") wants to say that the input a b
was expected but because it optional it is only a possibility, not a requirement.
I don't know possible is the same as expected or not?
Which error message better and correct: The 1st or the 2nd version?
Thanks for answers.
Second Part
In first case I define marker of testing
as limit of position.
if(_inputPos > testing) {
_failure(_inputPos, _code[cp + {{OFFSET_RESULT}}]);
}
Limit moved in optional expressions:
OPTIONAL_EXPRESSION:
testing = _inputPos;
The "b" expression move _inputPos
above the testing
pos and add failure at _inputPos
.
In second case I can define marker of testing
as boolean flag.
if(!testing) {
_failure(_inputPos, _code[cp + {{OFFSET_RESULT}}]);
}
The "b" expression in this case not add failure because it tested (inner for optional expression).
What you think what is better and correct?
Testing defined as specific position and if expression above this position (_inputPos > testing) it add failure (even it inside optional expression).
Testing defined as flag and if this flag set that the failures not takes into account. After executing optional expression it restore (not reset!) previous value of testing (true or false).
Also failures not takes into account if rule not fails. They only reported if parsing fails.
Third Part
This question raised because it related to two different problems.
First problem:
A Parsing Expression Grammar (PEG) describes input in only three atomic items:
- terminal symbol
- nonterminal symbol
- empty string
The grammar doesn't use a lexer, hence the concept of a “token” does not apply here.
Second problem:
What is a grammar? Can two grammars be considered equal if they accept the same input but produce different result?
Assume we have two grammars:
Grammar 1
rule <- type? identifier
Grammar 2
rule <- type identifier / identifier
They both accept the same input but produce (in PEG) different result.
Grammar 1 results:
{type: type, identifier: identifier}
{type: null, identifier: identifier}
Grammar 2 results:
{type: type, identifier: identifier}
{identifier: identifier}
Questions:
- Are both grammars equal?
- It is painless to do optimization of grammars?
My answer on both questions is negative. No equal, Not painless.
But you may ask. "But why this happens?".
I can answer to you. "Because this is not a problem. This is a feature".
In a PEG grammar each rule always consists from these parts:
- ordered choice
- sequence
- expression
- sequence
And this explanation is the my answer on question "But why this happens?".
Another problem.
As a PEG does not have tokens, whitespace cannot be silently ignored in the lexer between tokens. Therefore whitespace has to be considered inside the grammar. Now look at this grammar (in short):
program <- WHITESPACE expr EOF
expr <- ruleX
ruleX <- 'X' WHITESPACE
WHITESPACE <- ' '?
EOF <- ! .
The first WHITESPACE
is at the beginning, other `WHITESPACE (often) occurs at the end of a rule.
In this case in PEG optional WHITESPACE
must be assumed as expected.
But WHITESPACE
does not only mean space (\x20
) but also other characters like [\t\n\r]
and even comments.
But the main rule of error messages is the following.
If it is not possible to display all expected elements (or not possible to display at least one from all set of expected elements) then is more correct to not display anything.
More precisely required to display "unexpected" error mesage.
So how would I display in a PEG's error message that WHITESPACE
was expected?
Parser error: expected WHITESPACE
Parser error: expected ' ', '\t', '\n' , 'r'
What about start characters of comments? They also may be part of WHITESPACE
in some grammars.
In this case optional WHITESPACE will be reject all other potential expected elements because not possible correctly to display WHITESPACE in error message because WHITESPACE is too complex to display.
Is this good or bad?
I think this is not bad and required some tricks to hide this nature of PEG parsers.
And in my PEG parser I not assume that the inner expression at first position of optional (optional & zero_or_more) expression must be treated as expected. But all other inner (except at the first position) must treated as expected.
Example 1:
List<int list; // type? ident
Here "List" is not at the first position in optional "type?".
This failure is taken into account and reported as "expected '>'". This is because we don't skip type
but enter into type
and after really optional "List" we move position from first to next real "expected" (that already outside of testing position) element.
"List" was in "testing" position.
If inner expression (inside optional expression) "fits in the limitation" not continue at next position then it not assumed as the expected input.
From this assumption has been asked main question.
You must just take into account that we are talking about PEG parsers and their error messages.
(ab)?ac
or the EBNF[ "a", "b" ], "a", "c"
.rule: a b a c | a c
. Now for each alternative you can remember what caused the failure. If all alternatives have been exhausted, throw an error listing all reasons.