:: krowemoh

Friday | 13 DEC 2024
Posts Links Other About Now

previous
next

Yacc Shaving - Stage 1

2022-08-27

A link came up on hn:

https://archive.org/details/UnixProgrammingEnviornment

https://news.ycombinator.com/item?id=32604322

and in the comments someone mentioned that chapter 8 kind of goes off the rails with the implementation of BASIC using yacc. I know yacc is used to create languages but everything I've read makes it sound very complex. Here is a yacc example as a single chapter in a book about unix. I figured now would be the best time to give it a shot. The entire chapter is from page 233 - page 289. The first stage is from page 234 to page 242.

The chapter is going to build a relatively complex program in a series of stages. Stage 1 is a simple 4 function calculator which they have the entire code for in the text.

I wrote it out and it seems pretty straightforward. It also works right off the bat for the most part. I did need to make a modification to use float instead of double and I had to remove the formatting in the scanf command. I'm sure this has to do with my version of gcc.

$ cc -v
...
gcc version 4.8.5 20150623 (Red Hat 4.8.5-44) (GCC)

The full code in hoc1.y, this includes the exercise and additions:

%{
#define YYSTYPE float 
#include <math.h>
%}
%token NUMBER
%token UNARYMINUS
%left '+' '-'
%left '*' '/'
%left '%'
%left '^'
%left UNARYMINUS
%%
list: 
    | list '\n'
    | list expr '\n' { printf("s=> \t%.8g\n",$2); }
    ;
expr:   NUMBER          { $$ = $1; }
    | '+' expr      %prec UNARYMINUS { $$ = $2; }
    | '-' expr      %prec UNARYMINUS { $$ = -$2; }
    | expr '+' expr     { $$ = $1 + $3; }
    | expr '-' expr     { $$ = $1 - $3; }
    | expr '*' expr     { $$ = $1 * $3; }
    | expr '/' expr     { $$ = $1 / $3; }
    | expr '%' expr     { $$ = fmod($1,$3); }
    | expr '^' expr     { $$ = pow($1,$3); }
    | '(' expr ')'     { $$ = $2; }
    ;
%%

#include <stdio.h>
#include <ctype.h>
#include <math.h>
char *progname;
int lineno = 1;

main(argc, argv) 
    char *argv[];
{
    progname = argv[0];
    yyparse();
}

yylex()
{
    int c;
    while ((c=getchar()) == ' ' || c == '\t');
    if (c == EOF) return 0;

    if (c == '.' || isdigit(c)) {
        ungetc(c,stdin);
        scanf("%f",&yylval);
        printf("%c %f\n", c, yylval);
        return NUMBER;
    }

    if (c == '\n') lineno++;
    return c;
}

yyerror(s) 
    char *s;
{
    warning(s, (char *) 0);
}

warning(s,t)
    char *s, *t;
{
    fprintf(stderr, "%s: %s", progname, s);
    if (t) fprintf(stderr, " %s", t);
    fprintf(stderr, "near line %d\n", lineno);
}

My modifications are labeled with =>. I added a few extra print statements just to see how things were looking. Interesting as it seems that a yacc file is a mixture of C and yacc specific code. The functions like yylex I'm guessing are hooking into yacc specific stuff. This is a neat way of building parsers and using a tool. I've never done something like this where I work in conjunction with another program and write functions that overlap the other program.

Though now that I saw that, this is exactly how modern JS works, you have specific functions like mount cycle functions that you fill with your code and then frameworks like react will call your functions instead of it's own.

Everything old is new and everything new I have no idea the history about :)

Another note is the ungetc function is quite beautiful here. I really enjoyed seeing that as the next character got consumed during the if check but then gets put back so that scanf can grab it. I wonder why do that when you can take the character and assign it directly to yylval.

        scanf("%f",&yylval);

This reads in the character and puts it in the address referred to by yylval. I imagine if I knew another method of doing that, I could use that but I don't know enough C.

These are the commands that the book uses to build the project:

$ yacc hoc1.y
$ cc y.tab.c -o hoc1 -lm

I added -lm to be able to add the modulo and exponent operators.

The output:

$ ./hoc1
1+2
1 1.000000
2 2.000000
s=>     3
5*(4-2)
5 5.000000
4 4.000000
2 2.000000
s=>     10
2/3*3
2 2.000000
3 3.000000
3 3.000000
s=>     2
2^2-3
2 2.000000
2 2.000000
3 3.000000
s=>     1
3^3-10
3 3.000000
3 3.000000
1 10.000000
s=>     17
4+2^3-4
4 4.000000
2 2.000000
3 3.000000
4 4.000000
s=>     8

Voila! A quick and easy calculator built using yacc.

This was a fun little project. I'm going to next give the stage 2 a shot.