Lexical analysis with Lex (10 points)

[Leksikalsk analyse med Lex]

The following excerpt from “The C Programming Language” [2nd ed., B.W.
Kernighan, D.M. Ritchie, Prentice Hall 1988] describes the definition of integer constants
in C programs:

[Følgende utdrag fra “The C Programming Language” beskriver definisjonen av
heltallskonstanter i C-programmer:]

A2.5.1 Integer constants
 An integer constant consisting of a sequence of digits is taken
to be octal if it begins with 0 (digit zero), decimal otherwise.
Octal constants do not contain the digits 8 or 9. A sequence of digits
preceded by 0x or 0X (digit zero) is taken to be a hexadecimal integer.
The hexadecimal digits include a or A through f or F with values 10
through 15.

 An integer constant may be suffixed by the letter u or U, to
specify that it is unsigned. It may also be suffixed by the letter
l or L to specify that it is long.
[...]

Given the skeleton Lex specification below, fill in patterns and actions to
return a token value such that the main() function correctly classifies an integer
constant from standard input. (Use spare sheets if necessary.)

[Med utgangspunkt i den skisserte Lex-spesifikasjonen nedenfor, fyll inn patterns
og actions for å returnere en tokenverdi slik at funksjonen main() klassifiserer en
heltaltskonstant fra standard input korrekt. (Bruk tilleggsark om nødvendig.) ]

%{
#include <stdio.h>
#include <stdlib.h>

enum {
    OCT, U_OCT, L_OCT, U_L_OCT,
    HEX, U_HEX, L_HEX, U_L_HEX,
    INT, U_INT, L_INT, U_L_INT,
    WRONG
};
%}

%%

%%
int yywrap ( void ) { return 1; }
int main ( int argc, char **argv )
{
    switch ( yylex() )
    {
        case OCT        : printf ( "Octal\n" ); break;
        case U_OCT      : printf ( "Unsigned octal\n" ); break;
        case L_OCT      : printf ( "Long octal\n" ); break;
        case U_L_OCT    : printf ( "Unsigned long octal\n" ); break;
        case HEX        : printf ( "Hexadecimal\n" ); break;
        case U_HEX      : printf ( "Unsigned hexadecimal\n" ); break;
        case L_HEX      : printf ( "Long hexadecimal\n" ); break;
        case U_L_HEX    : printf ( "Unsigned long hexadecimal\n" ); break;
        case INT        : printf ( "Integer\n" ); break;
        case U_INT      : printf ( "Unsigned integer\n" ); break;
        case L_INT      : printf ( "Long integer\n" ); break;
        case U_L_INT    : printf ( "Unsigned long integer\n" ); break;
        default: printf ( "No match\n" ); break;
        
    }
    exit ( EXIT_SUCCESS );
}

Low-level programming and Yacc (25 points)

[Lavnivåprogrammering og Yacc]

 Uncommenting the commented printf-statements in the action rules makes
the yacc specification below translate (integer) expressions from infix notation to
postfix notation (e.g. “2*5-4” into “2 5 * 4 -”), suitable for stack machines.
 Fill in rules to make the program generate IA32 assembler code which evaluates
expressions using the stack. (Use spare sheets if necessary.)

[Om man fjerner utkommenteringen av printf-setningene i action-reglene, vil
Yacc-spesifikasjonen nedenfor oversette (heltalls-) uttrykk fra infiksnotasjon til
postfiksnotasjon (f.eks. “2*5-4” til “2 5 * 4 -”), som passer for stackmaskiner.
 Fyll in regler slik at programmet genererer IA32 assemblerkode som evaluerer
uttrykk ved bruk av stack. (Bruk tilleggsark om nødvendig.)]

• You may restrict evaluation to 32-bit integers (the code in the ASM_HEAD
macro initializes %edx to 0)
• At completion, the result should be the last value on stack (the code in
the ASM_TAIL macro prints the value there).
• You may ignore error handling, and assume that there is a suitable lexical
analyzer which emits integers and single-character operators only.

[
• Evalueringen trenger bare å ta hensyn til 32-bit heltall (koden i makroen 
ASM_HEAD initialiserer %edx til 0)
• Ved avslutning skal resultatet være siste verdi på stack (koden i makroen
ASM_TAIL skriver ut verdien derifra).
• Feilbehandling kan overses, og du kan anta at det finnes en passelig
leksikalsk analysator som bare sender heltall og operatorer på ett tegn.
]

Small instruction set reminder:
[Liten påminnelse om noen instruksjoner:]

movl %eax,(%esp)	- Move %eax into (%esp)		[Flytt %eax til (%esp)]
addl %eax,(%esp)	- Add %eax to (%esp)			[Legg %eax til (%esp)]
pushl %eax		- Push %eax onto stack		[Skyv %eax på stack]
imull (%esp)		- Multiply [%edx:%eax] with (%esp)	[Gang [%edx:%eax] med (%esp)]
idivl (%esp)		- Divide [%edx:%eax] with (%esp)	[Del [%edx:%eax] på (%esp)]

Program:

%{
#include <stdio.h>
#include <stdlib.h>

#define ASM_HEAD "\
.data\n\
OUT: .string \"%%d\\n\"\n\
.text\n\
.globl main\n\
main:\n\
pushl %%ebp\n\
movl  %%esp, %%ebp\n\
subl  $8, %%esp\n\
andl  $-16, %%esp\n\
movl $0, %%edx\n\
"

#define ASM_TAIL "\
pushl $OUT\n\
call printf\n\
addl $8,%%esp\n\
pushl $0\n\
call exit\n\
"
%}
%token INTEGER NEWLINE
%left '+' '-'
%left '*' '/'
%right UMINUS

%%
lines:
      lines expr NEWLINE
    | lines NEWLINE
    | /* e */
    ;
expr:
      expr '+' term { // printf ( "+ " );

      }
    | expr '-' term { // printf ( "- " );

      }
    | term
    ;
term:
      term '*' factor { // printf ( "* " );

      }
    | term '/' factor { // printf ( "/ " );

      }
    | factor
    ;
factor:
      '(' expr ')'
    | INTEGER { // printf ( "%d ", $1 );

      }
    | '-' INTEGER %prec UMINUS { // printf ( "-%d ", $1 );

      }
    ;
%%

int yyerror ( void ) { return 1; }

int main ( int argc, char **argv )
{   printf ( ASM_HEAD );    // Print the head of the program
    yyparse();              // Parse our input and emit code
    printf ( ASM_TAIL );    // Print the tail of the program
    exit ( EXIT_SUCCESS );  // Halt
}