b) What is the difference between a deterministic finite state machine or deterministic finite automaton (DFA) (in Swedish: "deterministisk ändlig tillståndsmaskin", "deterministisk finit automat") and a non-deterministic finite state machine or non-deterministic finite automaton (in Swedish: "icke-deterministisk ändlig tillståndsmaskin", "icke-deterministisk finit automat")?
// Counts the number of words in the input
// A word is a sequence of letters
#include <stdio.h>
#include <ctype.h>
int main(void) {
int c;
int number_of_words = 0;
int inside_a_word = 0;
while ((c = getchar()) != EOF) {
if (!isalpha(c)) {
// This was not a letter
inside_a_word = 0;
}
else if (!inside_a_word) {
// This was a letter, AND we were not (yet) inside a word
++number_of_words;
inside_a_word = 1;
}
}
printf("Number of words: %d\n", number_of_words);
return 0;
} // main
Soon (when I write this) it will be Halloween. Children celebrate the day by going "trick-or-treating". They go from door to door in the neighborhood and ask "trick or treat". To document this "candy round", they need a special Halloween language. A complete input might look like this:
began candy round; treat: three candies; trick: made some spooky sounds; treat: one kilo of chocolate; treat: a carrot; trick: set fire to the neighbors car; went home;
The input describes a candy round. It starts with began candy round; and ends with went home;. In between, there are zero or more notes about trick or treat. Such a note begins with either trick or treat, a colon (:), one or more words that indicate what happened, and a semicolon (;).
It should be possible to write the input in free format, such as in most common programming languages, for example like this:
Here is a Bison parser input file for the Halloween language.began candy round ; treat : three candies ; trick : made some spooky sounds ; treat : one kilo of chocolate ; treat : a carrot ; trick : set fire to the neighbors car ; went home ;
%{
#include <stdio.h>
extern void yyerror(const char *);
extern int yylex(void);
%}
%token BEGAN CANDY ROUND SEMICOLON TRICK TREAT COLON WORD WENT HOME
%define parse.error verbose
%start candy_round
%%
candy_round : BEGAN CANDY ROUND SEMICOLON trick_or_treat_list WENT HOME SEMICOLON
;
trick_or_treat_list: trick_or_treat trick_or_treat_list
| /* empty */
;
trick_or_treat : TRICK COLON word_list SEMICOLON
| TREAT COLON word_list SEMICOLON
;
word_list : WORD
| WORD word_list
;
%%
int main() {
printf("Enter a complete candy round. Finsih with EOF.\n");
yyparse();
printf("Done!\n");
return 0;
}
void yyerror(const char *s) {
printf("Invalid candy round! Error message: %s\n", s);
}
int yywrap(void) {
return 1;
}
a)
One of the terminals, that is, types of tokens,
that are used in the Halloween language
is word.
That is simply one or more lower-case letters, a to z.
(We only use the English alphabet.)
Write a regular expression that describes what such a word can look like.
b) Which other terminals, except word, are used in the language?
c) Write a Flex specification (the ".l" input file) for a scanner for the language.
d) Build a complete working program and check that it understands the Halloween language.
If the Flex input file is called halloween.l and the Bison input file is called halloween.y, the complete program can be built using these commands:
flex halloween.l bison -d halloween.y gcc -o halloween -Wall -Wextra halloween.tab.c lex.yy.c