Compiler/lexical analyzer: Difference between revisions
m Use entity for ; under symbols, so that it aligns left. |
m Better regular expressions for character and string literals. |
||
Line 58: | Line 58: | ||
| } || right brace || Rbrace |
| } || right brace || Rbrace |
||
|- |
|- |
||
| ; |
| ; || semi colon || Semi |
||
|- |
|- |
||
| , || comma || Comma |
| , || comma || Comma |
||
Line 86: | Line 86: | ||
| integers || [0-9]+ || Integer |
| integers || [0-9]+ || Integer |
||
|- |
|- |
||
| char literal || ' |
| char literal || <pre>'([^'\n]|\\n|\\\\)'</pre> || Integer |
||
|- |
|- |
||
| identifiers || [_a-zA-Z][_a-zA-Z0-9] |
| identifiers || [_a-zA-Z][_a-zA-Z0-9]* || Ident |
||
|- |
|- |
||
| string literal || " |
| string literal || "[^"\n]*" || String |
||
|} |
|} |
||
Line 182: | Line 182: | ||
! Output |
! Output |
||
|- |
|- |
||
| style="vertical-align:top" | |
| style="vertical-align:top" | |
||
<lang c> |
<lang c> |
||
/* |
/* |
Revision as of 15:05, 15 August 2016
Definition from Wikipedia:
- Lexical analysis is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an identified "meaning"). A program that performs lexical analysis may be called a lexer, tokenizer, or scanner (though "scanner" is also used to refer to the first stage of a lexer).
Create a lexical analyzer for the simple programming language specified below. The program should read input from a file and/or stdin, and write output to a file and/or stdout. If the language being used has a lexer module/library/class, it would be great if two versions of the solution are provided: One without the lexer module, and one with.
The simple programming language to be analyzed is more or less a subset of C. It supports the following tokens:
- Operators
Characters | Common name | Name |
---|---|---|
* | multiply | Mul |
/ | divide | Div |
+ | plus | Add |
- | minus and unary minus | Sub and Uminus |
< | less than | Lss |
<= | less than or equal | Leq |
> | greater than | Gtr |
!= | not equal | Neq |
= | assign | Assign |
&& | and | And |
- Symbols
Characters | Common name | Name |
---|---|---|
( | left parenthesis | Lparen |
) | right parenthesis | Rparen |
{ | left brace | Lbrace |
} | right brace | Rbrace |
; | semi colon | Semi |
, | comma | Comma |
- Keywords
Characters | Name |
---|---|
if | If |
while | While |
putc | Putc |
- Other entities
Characters | Regular expression | Name |
---|---|---|
integers | [0-9]+ | Integer |
char literal | '([^'\n]|\\n|\\\\)' |
Integer |
identifiers | [_a-zA-Z][_a-zA-Z0-9]* | Ident |
string literal | "[^"\n]*" | String |
Notes: For char and string literals, \n
is supported as a new line character. To represent a backslash, use \\
. No other special sequences are supported.
- White space
The following programs are equivalent:
<lang c> count = 1 ; n = 1 ; limit = 100 ; while ( n < limit ) {
k = 3 ; p = 1 ; n = n + 2 ; while ( ( k * k <= n ) && ( p ) ) { p = n / k * k != n ; k = k + 2 ; } if ( p ) { print ( n , " " ) ; count = count + 1 ; }
} print ( count , "\n" ) ; </lang>
<lang c> count=1;n=1;limit=100;while(n<limit){k=3;p=1;n=n+2;while((k*k<=n)&&(p)){p=n/k*k!=n;k=k+2;}if(p){print(n," ");count=count+1;}}print(count,"\n"); </lang>
They should produce the same token stream, except for the line and column positions.
Comments enclosed in /* ... */
are also treated as whitespace outside of strings.
- Complete list of token names
EOI Print Putc If While Lbrace Rbrace Lparen Rparen Uminus Mul Div Add Sub Lss Gtr Leq Neq And Semi Comma Assign Integer String Ident
The program output should be a sequence of lines, each consisting of the following whitespace-separated fields:
line
- the line number where the token starts
col
- the column number where the token starts
- the token name
- the token value, in case of Integer, String, or Ident
The following error conditions should be caught:
Error | Example |
---|---|
Empty character constant | ''
|
Unknown escape sequence. | \r
|
Multi-character constant. | 'xx'
|
End-of-file in comment. Closing comment characters not found. | |
End-of-file while scanning string literal. Closing string character not found. | |
End-of-line while scanning string literal. Closing string character not found before end-of-line. | |
Unrecognized character. |
Input | Output |
---|---|
<lang c> /* Hello world */ print("Hello, World!\n"); </lang> |
line 4 col 1 Print line 4 col 6 Lparen line 4 col 7 String "Hello, World!\n" line 4 col 24 Rparen line 4 col 25 Semi line 5 col 1 EOI |
<lang c> /* Show Ident and Integers */ phoenix_number = 142857; print(phoenix_number, "\n"); </lang> |
line 4 col 1 Ident phoenix_number line 4 col 16 Assign line 4 col 18 Integer 142857 line 4 col 24 Semi line 5 col 1 Print line 5 col 6 Lparen line 5 col 7 Ident phoenix_number line 5 col 21 Comma line 5 col 23 String "\n" line 5 col 27 Rparen line 5 col 28 Semi line 6 col 1 EOI |
<lang c> /* All lexical tokens - not syntactically correct, but that will have to wait until syntax analysis */ /* Print */ print /* Sub */ - /* Putc */ putc /* Lss */ < /* If */ if /* Gtr */ > /* While */ while /* Leq */ <= /* Lbrace */ { /* Neq */ != /* Rbrace */ } /* And */ && /* Lparen */ ( /* Semi */ ; /* Rparen */ ) /* Comma */ , /* Uminus */ - /* Assign */ = /* Mul */ * /* Integer */ 42 /* Div */ / /* String */ "String literal" /* Add */ + /* Ident */ variable_name /* character literal */ '\n' /* character literal */ ' ' </lang> |
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 19 col 1 EOI |
The Flex, C, Python and Euphoria versions can be considered reference implementations.
C
Tested with gcc 4.81 and later, compiles warning free with -Wall -Wextra <lang C>
- include <stdlib.h>
- include <stdio.h>
- include <stdarg.h>
- include <ctype.h>
- include <string.h>
- include <errno.h>
- include <stdbool.h>
- include <limits.h>
- define NELEMS(arr) (sizeof(arr) / sizeof(arr[0]))
- define da_dim(name, type) type *name = NULL; \
int _qy_ ## name ## _p = 0; \ int _qy_ ## name ## _max = 0
- define da_rewind(name) _qy_ ## name ## _p = 0
- define da_redim(name) if (_qy_ ## name ## _p >= _qy_ ## name ## _max) \
name = realloc(name, (_qy_ ## name ## _max += 32) * sizeof(name[0]))
- define da_append(name, x) do {da_redim(name); name[_qy_ ## name ## _p++] = x;} while (0)
- define da_len(name) _qy_ ## name ## _p
// dependancy: atr table in parse.c ordering is based on these typedef enum {
EOI, Print, Putc, If, While, Lbrace, Rbrace, Lparen, Rparen, Uminus, Mul, Div, Add, Sub, Lss, Gtr, Leq, Neq, And, Semi, Comma, Assign, Integerk, Stringk, Ident
} TokenType;
typedef struct {
int tok; int err_ln, err_col; union { int n; /* value for constants */ char *text; /* text for idents */ };
} tok_s;
static FILE *source_fp, *dest_fp; static int line = 1, col = 0, the_ch = ' '; da_dim(text, char);
tok_s gettok();
static void error(int err_line, int err_col, const char *fmt, ... ) {
char buf[1000]; va_list ap;
va_start(ap, fmt); vsprintf(buf, fmt, ap); va_end(ap); printf("(%d,%d) error: %s\n", err_line, err_col, buf); exit(1);
}
static int next_ch() { /* get next char from input */
the_ch = getc(source_fp); ++col; if (the_ch == '\n') { ++line; col = 0; } return the_ch;
}
static tok_s char_lit(int n, int err_line, int err_col) { /* 'x' */
if (the_ch == '\) error(err_line, err_col, "gettok: empty character constant"); if (the_ch == '\\') { next_ch(); if (the_ch == 'n') n = 10; else if (the_ch == '\\') n = '\\'; else error(err_line, err_col, "gettok: unknown escape sequence \\%c", the_ch); } if (next_ch() != '\) error(err_line, err_col, "multi-character constant"); next_ch(); return (tok_s){Integerk, err_line, err_col, {n}};
}
static tok_s div_or_cmt(int err_line, int err_col) { /* process divide or comments */
if (the_ch != '*') return (tok_s){Div, err_line, err_col, {0}};
/* comment found */ for (;;) { if (next_ch() == '*' && next_ch() == '/') { next_ch(); return gettok(); } else if (the_ch == EOF) error(err_line, err_col, "EOF in comment"); }
}
static tok_s string_lit(int start, int err_line, int err_col) { /* "st" */
da_rewind(text);
while (next_ch() != start) { if (the_ch == '\n') error(err_line, err_col, "EOL in string"); if (the_ch == EOF) error(err_line, err_col, "EOF in string"); da_append(text, (char)the_ch); } da_append(text, '\0');
next_ch(); return (tok_s){Stringk, err_line, err_col, {.text=text}};
}
static int kwd_cmp(const void *p1, const void *p2) {
return strcmp(*(char **)p1, *(char **)p2);
}
static TokenType get_ident_type(const char *ident) {
static struct { char *s; TokenType sym; } kwds[] = { {"if", If}, {"print", Print}, {"putc", Putc}, {"while", While}, }, *kwp;
return (kwp = bsearch(&ident, kwds, NELEMS(kwds), sizeof(kwds[0]), kwd_cmp)) == NULL ? Ident : kwp->sym;
}
static tok_s ident_or_int(int err_line, int err_col) {
int n, is_number = true;
da_rewind(text); while (isalnum(the_ch) || the_ch == '_') { da_append(text, (char)the_ch); if (!isdigit(the_ch)) is_number = false; next_ch(); } if (da_len(text) == 0) error(err_line, err_col, "gettok: unrecognized character (%d) '%c'\n", the_ch, the_ch); da_append(text, '\0'); if (isdigit(text[0])) { if (!is_number) error(err_line, err_col, "invalid number: %s\n", text); n = strtol(text, NULL, 0); if (n == LONG_MAX && errno == ERANGE) error(err_line, err_col, "Number exceeds maximum value"); return (tok_s){Integerk, err_line, err_col, {n}}; } return (tok_s){get_ident_type(text), err_line, err_col, {.text=text}};
}
static tok_s follow(int expect, TokenType ifyes, TokenType ifno, int err_line, int err_col) { /* look ahead for '>=', etc. */
if (the_ch == expect) { next_ch(); return (tok_s){ifyes, err_line, err_col, {0}}; } if (ifno == EOI) error(err_line, err_col, "follow: unrecognized character '%c' (%d)\n", the_ch, the_ch); return (tok_s){ifno, err_line, err_col, {0}};
}
tok_s gettok() { /* return the token type */
/* skip white space */ while (isspace(the_ch)) next_ch(); int err_line = line; int err_col = col; switch (the_ch) { case '{': next_ch(); return (tok_s){Lbrace, err_line, err_col, {0}}; case '}': next_ch(); return (tok_s){Rbrace, err_line, err_col, {0}}; case '(': next_ch(); return (tok_s){Lparen, err_line, err_col, {0}}; case ')': next_ch(); return (tok_s){Rparen, err_line, err_col, {0}}; case '+': next_ch(); return (tok_s){Add, err_line, err_col, {0}}; case '-': next_ch(); return (tok_s){Sub, err_line, err_col, {0}}; case '*': next_ch(); return (tok_s){Mul, err_line, err_col, {0}}; case ';': next_ch(); return (tok_s){Semi, err_line, err_col, {0}}; case ',': next_ch(); return (tok_s){Comma, err_line, err_col, {0}}; case '>': next_ch(); return (tok_s){Gtr, err_line, err_col, {0}}; case '=': next_ch(); return (tok_s){Assign, err_line, err_col, {0}}; case '/': next_ch(); return div_or_cmt(err_line, err_col); case '\: next_ch(); return char_lit(the_ch, err_line, err_col); case '<': next_ch(); return follow('=', Leq, Lss, err_line, err_col); case '!': next_ch(); return follow('=', Neq, EOI, err_line, err_col); case '&': next_ch(); return follow('&', And, EOI, err_line, err_col); case '"' : return string_lit(the_ch, err_line, err_col); default: return ident_or_int(err_line, err_col); case EOF: return (tok_s){EOI, err_line, err_col, {0}}; }
}
void run() { /* tokenize the given input */
tok_s tok; do { tok = gettok(); fprintf(dest_fp, "line %5d col %5d %.8s", tok.err_ln, tok.err_col, &"EOI Print Putc If While Lbrace Rbrace Lparen Rparen " "Uminus Mul Div Add Sub Lss Gtr Leq Neq " "And Semi Comma Assign Integer String Ident "[tok.tok * 9]);
if (tok.tok == Integerk) fprintf(dest_fp, " %4d", tok.n); else if (tok.tok == Ident) fprintf(dest_fp, " %s", tok.text); else if (tok.tok == Stringk) fprintf(dest_fp, " \"%s\"", tok.text); fprintf(dest_fp, "\n"); } while (tok.tok != EOI); if (dest_fp != stdout) fclose(dest_fp);
}
void init_io(FILE **fp, FILE *std, const char mode[], const char fn[]) {
if (fn[0] == '\0') *fp = std; else if ((*fp = fopen(fn, mode)) == NULL) error(0, 0, "Can't open %s\n", fn);
}
int main(int argc, char *argv[]) {
init_io(&source_fp, stdin, "r", argc > 1 ? argv[1] : ""); init_io(&dest_fp, stdout, "wb", argc > 2 ? argv[2] : ""); run(); return 0;
} </lang>
Output from test case 3:
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 19 col 1 EOI
Euphoria
Tested with Euphoria 4.05. <lang euphoria> include std/io.e include std/map.e include std/types.e include std/convert.e
constant true = 1, false = 0, EOF = -1
enum EOI, Printk, Putc, Ifk, Whilek, Lbrace, Rbrace, Lparen, Rparen, Uminus, Mul, Div,
Add, Sub, Lss, Gtr, Leq, Neq, Andk, Semi, Comma, Assign, Integerk, Stringk, Ident
constant all_syms = { "EOI", "Print", "Putc", "If", "While", "Lbrace", "Rbrace", "Lparen",
"Rparen", "Uminus", "Mul", "Div", "Add", "Sub", "Lss", "Gtr", "Leq", "Neq", "And", "Semi", "Comma", "Assign", "Integer", "String", "Ident"}
integer input_file, the_ch = ' ', the_col = 0, the_line = 1 sequence symbols map key_words = new()
procedure error(sequence format, sequence data)
printf(STDOUT, format, data) abort(1)
end procedure
-- get the next character from the input function next_ch()
the_ch = getc(input_file) the_col += 1 if the_ch = '\n' then the_line += 1 the_col = 0 end if return the_ch
end function
-- 'x' - character constants function char_lit(integer err_line, integer err_col)
integer n = next_ch() -- skip opening quote if the_ch = '\ then error("%d %d empty character constant", {err_line, err_col}) elsif the_ch = '\\' then next_ch() if the_ch = 'n' then n = 10 elsif the_ch = '\\' then n = '\\' else error("%d %d unknown escape sequence \\%c", {err_line, err_col, the_ch}) end if end if if next_ch() != '\ then error("%d %d multi-character constant", {err_line, err_col}) end if next_ch() return {Integerk, err_line, err_col, n}
end function
-- process divide or comments function div_or_cmt(integer err_line, integer err_col)
if next_ch() != '*' then return {Div, err_line, err_col} end if
-- comment found while true do if next_ch() = '*' and next_ch() = '/' then next_ch() return get_tok() elsif the_ch = EOF then error("%d %d EOF in comment", {err_line, err_col}) end if end while
end function
-- "string" function string_lit(integer start, integer err_line, integer err_col)
string text = ""
while next_ch() != start do if the_ch = EOF then error("%d %d EOF while scanning string literal", {err_line, err_col}) end if if the_ch = '\n' then error("%d %d EOL while scanning string literal", {err_line, err_col}) end if text &= the_ch end while
next_ch() return {Stringk, err_line, err_col, text}
end function
-- handle identifiers and integers function ident_or_int(integer err_line, integer err_col)
integer n, is_number = true string text = ""
while t_alnum(the_ch) or the_ch = '_' do text &= the_ch if not t_digit(the_ch) then is_number = false end if next_ch() end while
if length(text) = 0 then error("%d %d ident_or_int: unrecognized character: (%d) '%s'", {err_line, err_col, the_ch, the_ch}) end if
if t_digit(text[1]) then if not is_number then error("%d %d invalid number: %s", {err_line, err_col, text}) end if n = to_integer(text) return {Integerk, err_line, err_col, n} end if
if has(key_words, text) then return {get(key_words, text), err_line, err_col} end if
return {Ident, err_line, err_col, text}
end function
-- look ahead for '>=', etc. function follow(integer expect, integer ifyes, integer ifno, integer err_line, integer err_col)
if next_ch() = expect then next_ch() return {ifyes, err_line, err_col} end if
if ifno = EOI then error("%d %d follow: unrecognized character: (%d)", {err_line, err_col, the_ch}) end if
return {ifno, err_line, err_col}
end function
-- return the next token type function get_tok()
while t_space(the_ch) do next_ch() end while
integer err_line = the_line integer err_col = the_col
switch the_ch do case EOF then return {EOI, err_line, err_col} case '/' then return div_or_cmt(err_line, err_col) case '\ then return char_lit(err_line, err_col) case '<' then return follow('=', Leq, Lss, err_line, err_col) case '!' then return follow('=', Neq, EOI, err_line, err_col) case '&' then return follow('&', Andk, EOI, err_line, err_col) case '"' then return string_lit(the_ch, err_line, err_col) case else integer sym = symbols[the_ch] if sym != EOI then next_ch() return {sym, err_line, err_col} end if return ident_or_int(err_line, err_col) end switch
end function
procedure init()
put(key_words, "if", Ifk) put(key_words, "print", Printk) put(key_words, "putc", Putc) put(key_words, "while", Whilek)
symbols = repeat(EOI, 256) symbols['{'] = Lbrace symbols['}'] = Rbrace symbols['('] = Lparen symbols[')'] = Rparen symbols['+'] = Add symbols['-'] = Sub symbols['*'] = Mul symbols[';'] = Semi symbols[','] = Comma symbols['>'] = Gtr symbols['='] = Assign
end procedure
procedure main(sequence cl)
sequence file_name
input_file = STDIN if length(cl) > 2 then file_name = cl[3] input_file = open(file_name, "r") if input_file = -1 then error("Could not open %s", {file_name}) end if end if init() sequence t loop do t = get_tok() printf(STDOUT, "line %5d col %5d %-8s", {t[2], t[3], all_syms[t[1]]}) switch t[1] do case Integerk then printf(STDOUT, " %5d\n", {t[4]}) case Ident then printf(STDOUT, " %s\n", {t[4]}) case Stringk then printf(STDOUT, " \"%s\"\n", {t[4]}) case else printf(STDOUT, "\n") end switch until t[1] = EOI end loop
end procedure
main(command_line()) </lang>
Output from test case 3:
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 19 col 1 EOI
Flex
Tested with Flex 2.5.4. <lang C> %{
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include <errno.h>
- include <limits.h>
- define NELEMS(arr) (sizeof(arr) / sizeof(arr[0]))
typedef enum {
EOI, Print, Putc, If, While, Lbrace, Rbrace, Lparen, Rparen, Uminus, Mul, Div, Add, Sub, Lss, Gtr, Leq, Neq, And, Semi, Comma, Assign, Integer, String, Ident
} TokenType;
void yyerror(char msg[]) {
printf(msg); exit(1);
}
static int yynval;
struct yylloc {
int first_line, first_col; int last_line, last_col;
} yylloc;
static void update_loc() {
static int curr_line = 1; static int curr_col = 1;
yylloc.first_line = curr_line; yylloc.first_col = curr_col;
{char *s; for (s = yytext; *s != '\0'; s++) { if (*s == '\n') { curr_line++; curr_col = 1; } else { curr_col++; } }}
yylloc.last_line = curr_line; yylloc.last_col = curr_col-1;
}
- define YY_USER_ACTION update_loc();
static int kwd_cmp(const void *p1, const void *p2) {
return strcmp(*(char **)p1, *(char **)p2);
}
static TokenType get_ident_type(const char *ident) {
static struct { char *s; TokenType sym; } kwds[] = { {"if", If}, {"print", Print}, {"putc", Putc}, {"while", While}, }, *kwp;
return (kwp = bsearch(&ident, kwds, NELEMS(kwds), sizeof(kwds[0]), kwd_cmp)) == NULL ? Ident : kwp->sym;
}
%}
%start COMMENT2
%option noyywrap
digit [0-9] ident [a-zA-Z_][a-zA-Z_0-9]*
ascii_char [^\"\n] escaped_char \\n|\\\" number {digit}+ string_char {ascii_char}|{escaped_char} string \"({string_char})*\" char_const \'{string_char}\'
%%
<COMMENT2>[^*]+ ; <COMMENT2>\*[^/] ; <COMMENT2>\*\/ BEGIN 0; /* end comment */ "/*" BEGIN COMMENT2;
"{" {return Lbrace;} "}" {return Rbrace;} "(" {return Lparen;} ")" {return Rparen;} "*" {return Mul;} "/" {return Div;} "+" {return Add;} "-" {return Sub;} "<" {return Lss;} ">" {return Gtr;} "<=" {return Leq;} "!=" {return Neq;} "&&" {return And;} ";" {return Semi;} "," {return Comma;} "=" {return Assign;} {ident} {return get_ident_type(yytext);} {string} {return String;}
[ \t\n]+ ; /* ignore whitespace */
{number} {
yynval = strtol(yytext, NULL, 0); if (yynval == LONG_MAX && errno == ERANGE) yyerror("Number exceeds maximum value");
return Integer; }
{char_const} {
int n = yytext[1]; char *p = yytext;
if (yyleng < 3) yyerror("empty character constant"); ++p; if (p[0] == '\\') { ++p; if (p[0] == 'n') n = 10; else if (p[0] == '\\') n = '\\'; else yyerror("unknown escape sequence"); } yynval = n; return Integer; }
. yyerror("Unknown character\n");
%%
int main(int argc, char *argv[]) {
int tok;
++argv, --argc; /* skip over program name */ yyin = stdin; if (argc > 0) yyin = fopen(argv[0], "r");
do { tok = yylex(); printf("line %5d col %5d %.8s", yylloc.first_line, yylloc.first_col, &"EOI Print Putc If While Lbrace Rbrace Lparen Rparen " "Uminus Mul Div Add Sub Lss Gtr Leq Neq " "And Semi Comma Assign Integer String Ident "[tok * 9]);
if (tok == Integer) printf(" %4d", yynval); else if (tok == Ident) printf(" %s", yytext); else if (tok == String) printf(" %s", yytext); printf("\n"); } while (tok != EOI); return 0;
} </lang>
Output from test case 3:
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 18 col 29 EOI
FreeBASIC
Tested with FreeBASIC 1.05 <lang FreeBASIC> enum Token_type
tk_eoi tk_print tk_putc tk_if tk_while tk_lbrace tk_rbrace tk_lparen tk_rparen tk_uminus tk_mul tk_div tk_add tk_sub tk_lss tk_gtr tk_leq tk_neq tk_and tk_semi tk_comma tk_assign tk_integer tk_string tk_ident
end enum
const NewLine = chr(10) const DoubleQuote = chr(34)
' where we store keywords and variables type Symbol
s_name as string tok as Token_type
end type
dim shared symtab() as Symbol
dim shared cur_line as string dim shared cur_ch as string dim shared line_num as integer dim shared col_num as integer
function is_digit(byval ch as string) as long
is_digit = (ch <> "") and ch >= "0" and ch <= "9"
end function
function is_alnum(byval ch as string) as long
is_alnum = (ch <> "") and ((UCase(ch) >= "A" and UCase(ch) <= "Z") or (is_digit(ch)))
end function
sub error_msg(byval eline as integer, byval ecol as integer, byval msg as string)
print "("; eline; ":"; ecol; ")"; " "; msg system
end sub
' add an identifier to the symbol table function install(byval s_name as string, byval tok as Token_type) as integer
dim n as integer
n = ubound(symtab) redim preserve symtab(n + 1) n = ubound(symtab)
symtab(n).s_name = s_name symtab(n).tok = tok return n
end function
' search for an identifier in the symbol table function lookup(byval s_name as string) as integer
dim i as integer
for i = lbound(symtab) to ubound(symtab) if symtab(i).s_name = s_name then return i next return -1
end function
sub next_line() ' read the next line of input from the source file
cur_line = "" cur_ch = "" ' empty cur_ch means end-of-file if eof(1) then exit sub line input #1, cur_line cur_line = cur_line + NewLine line_num += + 1 col_num = 1
end sub
sub next_char() ' get the next char
cur_ch = "" col_num += 1 if col_num > len(cur_line) then next_line() if col_num <= len(cur_line) then cur_ch = mid(cur_line, col_num, 1)
end sub
function follow(byval err_line as integer, byval err_col as integer, byval expect as string, byval ifyes as Token_type, byval ifno as Token_type) as Token_type
if cur_ch = expect then next_char() return ifyes end if if ifno = tk_eoi then error_msg(err_line, err_col, "follow unrecognized character: " + cur_ch) return ifno
end function
sub gettok(byref err_line as integer, byref err_col as integer, byref tok as Token_type, byref v as string)
' skip whitespace do while (cur_ch = " " or cur_ch = chr(9) or cur_ch = NewLine) and (cur_ch <> "") next_char() loop
err_line = line_num err_col = col_num
select case cur_ch case "": tok = tk_eoi: exit sub case "{": tok = tk_lbrace: next_char(): exit sub case "}": tok = tk_rbrace: next_char(): exit sub case "(": tok = tk_lparen: next_char(): exit sub case ")": tok = tk_rparen: next_char(): exit sub case "+": tok = tk_add: next_char(): exit sub case "-": tok = tk_sub: next_char(): exit sub case "*": tok = tk_mul: next_char(): exit sub case ";": tok = tk_semi: next_char(): exit sub case ",": tok = tk_comma: next_char(): exit sub case ">": tok = tk_gtr: next_char(): exit sub case "=": tok = tk_assign: next_char(): exit sub case "/": ' div or comment next_char() if cur_ch <> "*" then tok = tk_div exit sub end if ' skip comments do next_char() if cur_ch = "*" or cur_ch = "" then next_char() if cur_ch = "/" or cur_ch = "" then next_char() gettok(err_line, err_col, tok, v) exit sub end if end if loop case "'": ' single char literals next_char() v = str(Asc(cur_ch)) if cur_ch = "'" then error_msg(err_line, err_col, "empty character constant") if cur_ch = "\" then next_char() if cur_ch = "n" then v = "10" elseif cur_ch = "\" then v = Str(Asc("\")) else error_msg(err_line, err_col, "unknown escape sequence: " + cur_ch) end if end if next_char() if cur_ch <> "'" then error_msg(err_line, err_col, "multi-character constant") next_char() tok = tk_integer exit sub case "<": next_char(): tok = follow(err_line, err_col, "=", tk_Leq, tk_Lss): exit sub case "!": next_char(): tok = follow(err_line, err_col, "=", tk_Neq, tk_EOI): exit sub case "&": next_char(): tok = follow(err_line, err_col, "&", tk_And, tk_EOI): exit sub case DoubleQuote: ' string v = cur_ch next_char() do while cur_ch <> DoubleQuote if cur_ch = NewLine then error_msg(err_line, err_col, "EOL in string") if cur_ch = "" then error_msg(err_line, err_col, "EOF in string") v += cur_ch next_char() loop v += cur_ch next_char() tok = tk_string exit sub case else ' integers or identifiers dim is_number as boolean = is_digit(cur_ch) v = "" do while is_alnum(cur_ch) orelse cur_ch = "_" if not is_digit(cur_ch) then is_number = false v += cur_ch next_char() loop if len(v) = 0 then error_msg(err_line, err_col, "unknown character: " + cur_ch) if is_digit(mid(v, 1, 1)) then if not is_number then error_msg(err_line, err_col, "invalid number: " + v) tok = tk_integer exit sub end if dim as integer index = lookup(v) if index = -1 then tok = tk_ident else tok = symtab(index).tok end if exit sub end select
end sub
sub init_lex(byval filein as string)
install("if", tk_if) install("print", tk_print) install("putc", tk_putc) install("while", tk_while)
open filein for input as #1
cur_line = "" line_num = 0 col_num = 0 next_char()
end sub
sub scanner()
dim err_line as integer dim err_col as integer dim tok as Token_type dim v as string dim tok_list(tk_eoi to tk_ident) as string
tok_list(tk_eoi ) = "EOI" tok_list(tk_print ) = "Print" tok_list(tk_putc ) = "Putc" tok_list(tk_if ) = "If" tok_list(tk_while ) = "While" tok_list(tk_lbrace ) = "Lbrace" tok_list(tk_rbrace ) = "Rbrace" tok_list(tk_lparen ) = "Lparen" tok_list(tk_rparen ) = "Rparen" tok_list(tk_uminus ) = "Uminus" tok_list(tk_mul ) = "Mul" tok_list(tk_div ) = "Div" tok_list(tk_add ) = "Add" tok_list(tk_sub ) = "Sub" tok_list(tk_lss ) = "Lss" tok_list(tk_gtr ) = "Gtr" tok_list(tk_leq ) = "Leq" tok_list(tk_neq ) = "Neq" tok_list(tk_and ) = "And" tok_list(tk_semi ) = "Semi" tok_list(tk_comma ) = "Comma" tok_list(tk_assign ) = "Assign" tok_list(tk_integer) = "Integer" tok_list(tk_string ) = "String" tok_list(tk_ident ) = "Ident"
do gettok(err_line, err_col, tok, v) print using "line ##### col ##### \ \"; err_line; err_col; tok_list(tok); if tok = tk_integer orelse tok = tk_ident orelse tok = tk_string then print " " + v; print loop until tok = tk_eoi
end sub
sub main()
if command(1) = "" then print "filename required" : system init_lex(command(1)) scanner()
end sub
main() system </lang>
Output from test case 3:
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 18 col 30 EOI
Python
Tested with Python 2.7 and 3.x <lang Python>
from __future__ import print_function import sys
- following two must remain in the same order
EOI, Print, Putc, If, While, Lbrace, Rbrace, Lparen, Rparen, Uminus, Mul, Div, Add, \ Sub, Lss, Gtr, Leq, Neq, And, Semi, Comma, Assign, Integerk, Stringk, Ident = range(25)
all_syms = [ 'EOI', 'Print', 'Putc', 'If', 'While', 'Lbrace', 'Rbrace', 'Lparen',
'Rparen', 'Uminus', 'Mul', 'Div', 'Add', 'Sub', 'Lss', 'Gtr', 'Leq', 'Neq', 'And', 'Semi', 'Comma', 'Assign', 'Integer', 'String', 'Ident' ]
- single character only symbols
symbols = { '{': Lbrace, '}': Rbrace, '(': Lparen, ')': Rparen, '+': Add, '-': Sub,
'*': Mul, ';': Semi, ',': Comma, '>': Gtr, '=': Assign }
key_words = { 'if': If, 'print': Print, 'putc': Putc, 'while': While }
the_ch = " " # dummy first char - but it must be a space the_col = 0 the_line = 1 input_file = None
- show error and exit
def error(line, col, msg):
print(line, col, msg) exit(1)
- get the next character from the input
def next_ch():
global the_ch, the_col, the_line
the_ch = input_file.read(1) the_col += 1 if the_ch == '\n': the_line += 1 the_col = 0 return the_ch
- 'x' - character constants
def char_lit(err_line, err_col):
n = ord(next_ch()) # skip opening quote if the_ch == '\: error(err_line, err_col, "empty character constant") elif the_ch == '\\': next_ch() if the_ch == 'n': n = 10 elif the_ch == '\\': n = '\\' else: error(err_line, err_col, "unknown escape sequence \\%c" % (the_ch)) if next_ch() != '\: error(err_line, err_col, "multi-character constant") next_ch() return Integerk, err_line, err_col, n
- process divide or comments
def div_or_cmt(err_line, err_col):
if next_ch() != '*': return Div, err_line, err_col
# comment found while True: if next_ch() == '*' and next_ch() == '/': next_ch() return gettok() elif len(the_ch) == 0: error(err_line, err_col, "EOF in comment")
- "string"
def string_lit(start, err_line, err_col):
text = ""
while next_ch() != start: if len(the_ch) == 0: error(err_line, err_col, "EOF while scanning string literal") if the_ch == '\n': error(err_line, err_col, "EOL while scanning string literal") text += the_ch
next_ch() return Stringk, err_line, err_col, text
- handle identifiers and integers
def ident_or_int(err_line, err_col):
is_number = True text = ""
while the_ch.isalnum() or the_ch == '_': text += the_ch if not the_ch.isdigit(): is_number = False next_ch()
if len(text) == 0: error(err_line, err_col, "ident_or_int: unrecognized character: (%d) '%c'" % (ord(the_ch), the_ch))
if text[0].isdigit(): if not is_number: error(err_line, err_col, "invalid number: %s" % (text)) n = int(text) return Integerk, err_line, err_col, n
if text in key_words: return key_words[text], err_line, err_col
return Ident, err_line, err_col, text
- look ahead for '>=', etc.
def follow(expect, ifyes, ifno, err_line, err_col):
if next_ch() == expect: next_ch() return ifyes, err_line, err_col
if ifno == EOI: error(err_line, err_col, "follow: unrecognized character: (%d) '%c'" % (ord(the_ch), the_ch))
return ifno, err_line, err_col
- return the next token type
def gettok():
while the_ch.isspace(): next_ch()
err_line = the_line err_col = the_col
if len(the_ch) == 0: return EOI, err_line, err_col elif the_ch == '/': return div_or_cmt(err_line, err_col) elif the_ch == '\: return char_lit(err_line, err_col) elif the_ch == '<': return follow('=', Leq, Lss, err_line, err_col) elif the_ch == '!': return follow('=', Neq, EOI, err_line, err_col) elif the_ch == '&': return follow('&', And, EOI, err_line, err_col) elif the_ch == '"': return string_lit(the_ch, err_line, err_col) elif the_ch in symbols: sym = symbols[the_ch] next_ch() return sym, err_line, err_col else: return ident_or_int(err_line, err_col)
- main driver
input_file = sys.stdin if len(sys.argv) > 1:
try: input_file = open(sys.argv[1], "r", 4096) except IOError as e: error(0, 0, "Can't open %s" % sys.argv[1])
while True:
t = gettok() tok = t[0] line = t[1] col = t[2]
print("line %5d col %5d %-8s" % (line, col, all_syms[tok]), end=)
if tok == Integerk: print(" %5d" % (t[3])) elif tok == Ident: print(" %s" % (t[3])) elif tok == Stringk: print(' "%s"' % (t[3])) else: print("")
if tok == EOI: break
</lang>
Output from test case 3:
line 5 col 15 Print line 5 col 41 Sub line 6 col 15 Putc line 6 col 41 Lss line 7 col 15 If line 7 col 41 Gtr line 8 col 15 While line 8 col 41 Leq line 9 col 15 Lbrace line 9 col 41 Neq line 10 col 15 Rbrace line 10 col 41 And line 11 col 15 Lparen line 11 col 41 Semi line 12 col 15 Rparen line 12 col 41 Comma line 13 col 15 Sub line 13 col 41 Assign line 14 col 15 Mul line 14 col 41 Integer 42 line 15 col 15 Div line 15 col 41 String "String literal" line 16 col 15 Add line 16 col 41 Ident variable_name line 17 col 26 Integer 10 line 18 col 26 Integer 32 line 19 col 1 EOI