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

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]

Return to the comp.compilers page.
Search the comp.compilers archives again.