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

Groups > comp.compilers > #1063 > unrolled thread

flex + yacc problem: partial parsing.

Back to article view | Back to comp.compilers

Contents

  flex + yacc problem: partial parsing. Kaz Kylheku <kaz@kylheku.com> - 2013-12-17 22:52 +0000
    Re: flex + yacc problem: partial parsing. Kaz Kylheku <kaz@kylheku.com> - 2014-01-07 23:56 +0000
    Re: flex + yacc problem: partial parsing. Kaz Kylheku <kaz@kylheku.com> - 2014-01-08 03:18 +0000
      Re: flex + yacc problem: partial parsing. Kaz Kylheku <kaz@kylheku.com> - 2014-01-08 18:29 +0000

#1063 — flex + yacc problem: partial parsing.

Does anyone have a nice hack (portable across Yacc implementations)
whereby multiple calls to yyparse() can be used to cleanly extract the major
constituents from a stream?

I'm running into the problem that yacc throws a syntax error when
there is extra material after the syntactic unit which it has parsed.

I not only want to suppress that error, but also not to have yacc read
ahead into the stream at all: not to ask for the next token. For instance if
the stream contains two expression slike (a b c) (x y z), I want the parser to
just extract (a b c) and leave the subsquent ( token alone (leaving
that for the next call to yyparse).

Essentially, what I want is LR(0) type behavior in cases where the only
possible action is a reduction, regardless of lookahead. I mean, the closing
parenthesis necessarily closes the expression *regardless of what follows*.
What follows could be the end of the stream, or any token.

Yacc's tables have this info. For some states, there is sometimes only the
default reduce action, and no shift actions: the whole table row is filled with
reduces.

But there is also the problem of the parser insisting on matching the pseudo
token $end. From Bison's y.output:

        state 30

            0 $accept: spec . $end

            $end  shift, and go to state 154


        state 154

            0 $accept: spec $end .

            $default  accept

In this particular case, I want something else. More like:

        state 30

            0 $accept: spec .

            $default accept

So in a nutshell, I want the parser not to read ahead any tokens in situations
where there is only a default reduce action with no shift, and not to constrain
the start symbol to be followed by $end.

--
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
[You can use YYACCEPT to tell yacc or bison that you're done parsing,
but I'm not sure about the readahead. -John]

[toc] | [next] | [standalone]

#1072

On 2013-12-17, John added:
> [You can use YYACCEPT to tell yacc or bison that you're done parsing,
> but I'm not sure about the readahead. -John]

Thanks a lot for that heads up.

I have done an experiment which shows that the readahead will in fact be
suppressed.

However, it requires cooperation from the grammar, so a trivial sprinkling of
YYACCEPT in my actual grammar doesn't do the trick. I already know quite
exactly what the reason is: in my grammar, an expr (that I'm trying to
extract) can be "expr DOTDOT expr" where DOTDOT is a .. operator.
For this reason, we cannot reduce expr to the start symbol without looking
ahead to see whether there is a DOTDOT token, and so by the time we get
to the rule associated with that reduction, the lookahead has taken place.

However, the following test program shows that lookadhead is not performed
unnecessarily to do a reduction which doesn't require it.

If we leave YYACCEPT commented out, then the message "token!" is printed
twice (showing that yylex is called twice) and there is a syntax error.
This is most likely because the parser is processing the embedded rule:

    0 $accept: S . $end

and the scanner has returned another FOO.

If we uncomment YYACCEPT, then yylex is called only once, and the parse
succeeds, showing that no lookahead was performed to achieve the reduction
of S <- FOO, and the $accept <- FOO $end reduction is nicely skipped.

I think I have enough info to make progress on this. Thanks again.

%{
#include "y.tab.h"
void yyerror(const char *str);
%}

%token FOO
%type<str> S

%%

S : FOO { /* YYACCEPT; */ };

%%

int yylex(void)
{
  puts("token!");
  return FOO;
}

void yyerror(const char *str)
{
  puts(str);
}

int main(void)
{
  yyparse();
}


--
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List:  http://www.kylheku.com/mp1

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

#1073

On 2013-12-17, Kaz Kylheku <kaz@kylheku.com> wrote:
> [You can use YYACCEPT to tell yacc or bison that you're done parsing,
> but I'm not sure about the readahead. -John]

Okay, I got it all working:

http://www.kylheku.com/cgit/txr/commit/?id=c5accb635a0892c685947aa0bb45193f4cd5cb38

In a nutshell:

- had to refactor the grammar so that that an expr can be reduced to the
  start symbol without any lookahead token, as a $default reduction:
  all entries in the parsing table say "reduce", regardless of
  the lookahead token. *-note

- had to add the YYACCEPT; trick to the top reduction.

- to completely solve the lookahead problem down to the lexical level
  (so after extracting an expr, the stream is left in the proper state so that
  another expr can be extracted), I had to change the YYINPUT macro
  to only return one byte at a time. If YYINPUT reads more than one
  byte from the stream, then these accumulated bytes will be thrown
  away when the lexical machine is reinitialized for another yyparse
  job.

----

* This is usually trivial in Lisp grammars, except that I support an
  a .. b operator which is a syntactic sugar for (cons a b), which means
  that if we parse the "a", we need lookahead to determine whether the
  next thing is "..", or EOF.  I refactored it by making the .. operator
  part of the syntax of a compound list expression; it cannot occur
  by itself any more, which is perfectly acceptable.  In other words,
  a .. b is now just syntax, on par with something like the consing
  dot notation, and not an independent expression.  You'd never want
  a top-level expression that is just the equivalent of (cons a b).

--
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List:  http://www.kylheku.com/mp1

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

#1076

On 2014-01-08, Kaz Kylheku <kaz@kylheku.com> wrote:
> On 2013-12-17, Kaz Kylheku <kaz@kylheku.com> wrote:
>> [You can use YYACCEPT to tell yacc or bison that you're done parsing,
>> but I'm not sure about the readahead. -John]
>
> Okay, I got it all working:

Furthermore, I'd like to add the small but significant note that it all works
with two different Yacc implementations: GNU Bison 2.5, as well as Berkeley
Yacc 1.9 (20110908).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web