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

Groups > comp.programming > #6950 > unrolled thread

Re: Parsing and reporting errors?

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#6950 — Re: Parsing and reporting errors?

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"

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [next] | [standalone]

#6951

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.

[toc] | [prev] | [next] | [standalone]

#6952

On 2016-09-30 18:03, Kaz Kylheku wrote:
> 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.

Simply because the language has lexemes? There is no Lexer in the sense 
of an operation that takes the input and produces an output (a sequence 
of lexemes), so that the next stage does not start until the output of 
lexer is complete.

> 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.

Not really, normally the parser simply matches the source against the 
current table of alternatives expected:

    switch (Statements.Match (Source))
    {
       case If_Statement :
          ...
       case When_Statement :
          ...
          ...
       default :
          Error
            << "One of keywords "
            << Image (Statements)
            << " is expected at "
            <<  Image (Source.Location);

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#6954

On 2016-09-30, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On 2016-09-30 18:03, Kaz Kylheku wrote:
>> 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.
>
> Simply because the language has lexemes? There is no Lexer in the sense 
> of an operation that takes the input and produces an output (a sequence 
> of lexemes), so that the next stage does not start until the output of 
> lexer is complete.

I see; in that case there is no lexer in a typical lex + yacc job,
because the function yylex is not repeatedly called to produce lexemes
which are then arranged into a sequence that is parsed in a second pass.

>> 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.
>
> Not really, normally the parser simply matches the source against the 
> current table of alternatives expected:
>     switch (Statements.Match (Source))
>     {

"the source" constitutes lookahead: the matcher has to peek into the
stream a number of characters, which stay there if there is no match.

[toc] | [prev] | [next] | [standalone]

#6955

On 2016-09-30 19:46, Kaz Kylheku wrote:
> On 2016-09-30, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:

>> Not really, normally the parser simply matches the source against the
>> current table of alternatives expected:
>>     switch (Statements.Match (Source))
>>     {
>
> "the source" constitutes lookahead: the matcher has to peek into the
> stream a number of characters, which stay there if there is no match.

In the sense that a source character might be tested several times. But 
the current line is read into memory anyway.

If the table uses hash that could be counted as a look-ahead too. But 
usually look-ahead means something more substantial.

Tiny brainless parsing stages make messages generation more difficult. 
The richer the context the better messages.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#6957

On 2016-09-30, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On 2016-09-30 19:46, Kaz Kylheku wrote:
>> On 2016-09-30, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>
>>> Not really, normally the parser simply matches the source against the
>>> current table of alternatives expected:
>>>     switch (Statements.Match (Source))
>>>     {
>>
>> "the source" constitutes lookahead: the matcher has to peek into the
>> stream a number of characters, which stay there if there is no match.
>
> In the sense that a source character might be tested several times. But 
> the current line is read into memory anyway.

Yes, and that part of the current line not read into the parser's
memory is in some stream buffer, and stuff not in the stream buffer
is in the TCP windows of the network connection, etc.

Any of it is "lookahead" or none, depending on how you define
the word.

> If the table uses hash that could be counted as a look-ahead too. But 
> usually look-ahead means something more substantial.

Usually "lookahead" in the context of parsing refers to something
meaningful in the parsing algorithm, irrespective of underlying
buffers and such. Specifically, "lookahead" refers to an item,
or multiple items, which are understood to have been removed from
the input stream and are under the control of the parsing algorithm.
In many circumstances when the parsing algorithm must process more
input, it must first process these lookahead items in preference to
subsequent input. (That may be done by pushing back the lookahead
items as characters back into the stream, if possible, or doing
something else.)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web