"Bootstrapping yacc in yacc" -> "Bootstrapping yacc in lex"!

[Rock Brentwood]

It's a recurrent question that's come up in other forums "can yacc be
bootstrapped in yacc?" Now, I'm adding a twist.

I'll repeat one of my recent replies here. In the syntax for yacc files, laid
out by the POSIX standard, there is no mandatory semi-colon at the ends of
rules, so an extra look-ahead is required to determine whether an identifier
is followed by a colon. If so, then this indicates the left-hand side of a new
rule.

A grammar rule has the form

left-hand-side ":" stuff on the right optional ";"'s.

If you see a ":" in the middle of the rules on the right, then you've actually
sneaked on over into the *next* rule.

Bison hacks the syntax, by making left-hand-side + ":" into a single token.

It may, in fact, be possible to parse yacc *even with* this issue, without
having to hack yacc grammar like bison did - by just simply not using yacc at
all, but using only lex!

The grammar specified by POSIX is actually a *regular* grammar that specifies
a finite state transducer. The transducer is deterministic, precisely because
the identifier-colon ambiguity can be resolved. Therefore, if you set up the
right kind of finite state machine in lex making use of lex's start condition
facility in the right way, then you should be able to parse a yacc grammar
with lex and to bootstrap an implementation of yacc with just lex.

A specification possibly suitable for utilities like lex (using UNICODE, in
UTF-8 format) - working off the POSIX syntax - can be found in comp.theory
here
https://groups.google.com/g/comp.theory/c/jSkl9ey7iM8

It comp.compilers can handle UTF-8, I can repeat it here, as well.
[Yes, messages are in UTF-8. -John]

[Kaz Kylheku]

On 2021-03-15, Rock Brentwood <rockbr...@gmail.com> wrote:
> It's a recurrent question that's come up in other forums "can yacc be
> bootstrapped in yacc?" Now, I'm adding a twist.
>
> I'll repeat one of my recent replies here. In the syntax for yacc files, laid
> out by the POSIX standard, there is no mandatory semi-colon at the ends of
> rules, so an extra look-ahead is required to determine whether an identifier
> is followed by a colon. If so, then this indicates the left-hand side of a new
> rule.
>
> A grammar rule has the form
>
> left-hand-side ":" stuff on the right optional ";"'s.
>
> If you see a ":" in the middle of the rules on the right, then you've actually
> sneaked on over into the *next* rule.
>
> Bison hacks the syntax, by making left-hand-side + ":" into a single token.

You could simply allow rules of this form

":" right side ...


With a semantic restrction that this must be preceded by a rule that
is not terminated with a semicolon, whose last element is a symbol:

blah ":" previous rule material ending in symbol /* no semicolon */

":" next rule ";"

Then we make the AST transformation of moving "symbol" to be the head
of the following rule:

-->


blah ":" previous rule material ending in

symbol ":" next rule ";"

Situations where it's not a symbol, or the prior rule has ended in
a semicolon (which is thus followed by a colon) are not syntax
errors, but are diagnosed semantically.
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal