Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6951

Re: Parsing and reporting errors?

Show all headers | View raw

On 2016-09-30, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On 2016-09-30 15:51, Stefan Ram wrote:
>>   A parser (syntactical analyser) gets tokens from the scanner
>>   (lexical analyser), which gets characters from a character source.
>>   (In terms of OOP, each of these, the parser, the scanner and
>>   the character source might be an individual object.)
>>
>>   It might happen that the parser detects a syntax error.
>>   How can it then report this?
>>
>>   Ok, it might print the token and a diagnostic message.
>>
>>   But the parser does not know the line and the offset in the
>>   line, so it can't print the line number and source context.
>>   This has already been abstracted away by the lower entities
>>   (the scanner and the character source). Usually, the parser
>>   does not need to know these lower-level details.
>>
>>   How does one usually deal with this? (Printing the line number,
>>   the line offset and the region of the source code where the
>>   error was detected when the parser detects an error)
>
> By not using lexers, of course. The parser scans the source, the current 
> location in the source describes everything necessary to generate 
> message, file name, line number, start character, end character. There 
> are two source location pointers one to end of the parsed part and 
> another to the beginning of the unparsed one. The space in-between in 
> the lexeme being analyzed.
>
>>   However, due to "lookahead" or some "buffering",
>>   the current position of the scanner might already
>>   be ahead of that current token of the parser.
>
> There is no need to do lookahead etc. When the recursive descent parser 
> goes down it can pass the location where it started, so that you can 
> report errors like "Closing bracket expected at xxx:xx for the opening 
> one at xxx:xx"

If your recursive descent parser has a function like

   if ((kw = maybe_keyword(context)) {
     switch (kw) {
     case KW_IF: ...
     case KW_DO: ...
     }
   } else ...

then you *effectively* have lexer: it consists of the
recursive descent functions that recognize /de facto/
tokens.

You can legitimately claim that you have no lexical
analysis distinct from parsing, when your recursive descent
cases switch on characters. For instance, if parsing C:

  switch (lookahead_char) {
  case 'i':
    parse_int_if_or_i_ident(context);
    /* ... */
  }

where parse_int_if_or_i handles the "int" and "if" keywords,
or any identifier starting with "i".

If your lexing is rolled into recursive descent, yes you
need lookahead: lots of it!

With tokenization, we can handle useful grammars with only
one symbol of lookahead, via {LA,}LR(1).

Without tokenization, symbols are just characters, that requires k
lookahead, where k is the longest ambiguous sequence of characters share
by different tokens.

For instance, the above maybe_keyword function has to scan
multiple characters. If they turn out not to be a keyword,
they all get pushed back into the stream, so that the
maybe_ident(context) call can do its job.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Parsing and reporting errors? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2016-09-30 17:17 +0200
  Re: Parsing and reporting errors? Kaz Kylheku <221-501-9011@kylheku.com> - 2016-09-30 16:03 +0000
    Re: Parsing and reporting errors? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2016-09-30 18:45 +0200
      Re: Parsing and reporting errors? Kaz Kylheku <221-501-9011@kylheku.com> - 2016-09-30 17:46 +0000
        Re: Parsing and reporting errors? "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2016-09-30 22:07 +0200
          Re: Parsing and reporting errors? Kaz Kylheku <221-501-9011@kylheku.com> - 2016-09-30 22:50 +0000

csiph-web