Hi,
I have something that looks like a Yacc [0]. Here is
what you guys can do:
+ play with it and find bugs
[0] https://github.com/mpu/ninja
+ fix the bugs you found!
+ criticize it
+ suggest me a better name
+ print it and use it as wallpaper
I did not decide on the license yet, I think I will make
it BSD/MIT.
This is one C file named 'miniyacc.c', and it weighs
about 1300 lines of code (including the template code
for the .tab.c files generation). This is bigger than
what I initially wanted, but remains fairly small. For
reference, it is half the size of Plan9 yacc.c, which
is about half the size of Berkeley Yacc.
Here is the list of (mis-)features:
- typical precedence and associativity support
- nice user friendly C char tokens (like '+' and '-')
- rules with 0 or 1 action, the action *has* to be
at the end, no middle actions are permitted (even
though POSIX allows them)
- unions and tags (it seems to be called typechecking
sometimes)
- inefficient (educational!) LALR(1) states generation;
modern computers are fast, ugly performance tricks for
that are now obsolete, I think (we'll see)
- nice and efficient table compression, I tested on
one or two grammars, it seems to be as efficient as
bison's!
- a botched parser for a subset of what POSIX defines;
it is at best very loose, and at worst a little buggy
- no support for comments, hahaha
- the -v option dumps nitty-gritty details in a .grm
file
- no yyerror stuff (in POSIX)
- in case of error, no cleanup is performed
- the current parsing stack is ridiculously small
It is very short, so it should be quite straightforward
to port it to other languages if you wish (especially
imperative lanuguages). On top of that, I plan to write
some documentation to detail the inners, so anybaody can
get a good idea of how it works (I did not really manage
to decipher Berkely and Plan9's Yacc.) This already
started a little in the 'doc.txt' file in the repo [0].
Since sbase does not have a Yacc, I thought that you
guys would be interested. In addition to being one
sbase element, it opens the door for implementing with
little pain some other language-based tools (awk, bc).
One could even envision a suckless C compiler or a
new suckless language.
For those excited by this kind of stuff, you can
find an idealized implementation for an LR parser
here:
https://github.com/mpu/parsexp/blob/master/eexp.c
It all started from there.
Happy hacking,
-- Quentin
