|need help with reg. expr., fsa email@example.com (1995-09-28)|
|Keywords:||DFA, lex, question|
|Date:||Thu, 28 Sep 1995 06:01:17 GMT|
i have no idea where to post this question. i thought about posting it
here, since most course on compiler design discuss regular expressions,
finite state automaton, and bnf grammar.
my question is this:
1) let us say you have a grammar which describes comments. comments consist
of strings surrounded by /* and */ without intervening */, unless that */
appears in single quotes '*/'. assume that the alphabet contains the five
characters: a b ' / *
so /*ab'*/ and /*ab'*/'a*/ are proper comments
but /*ab'*/aa and /*ab*/a*/ are not proper comments.
i've constructed a non-deterministic fsa for this. i am not sure how to
construct a bnf grammar or regular expression for this language.
for the regular expression, i thought of
(/*)(a | b | / | * | '*/')* (*/)
but the problem is in the middle expression - how do you know if the
comment string has * / and then something else?
for bnf, the grammar i came up with has the same problem - i'm not sure
how to handle checking what has occured already - this is easier with
2) write a regular expression for the set of binary numbers containing
3k 1's where k=1,2,3,... i need an fsa and ebnf (extended bnf) grammar
that recognizes this language.
general advice on how to handle these sort of problems would also be
Return to the
Search the comp.compilers archives again.