need help with reg. expr., fsa

khemani@eden.rutgers.edu (Maverick)
Thu, 28 Sep 1995 06:01:17 GMT

          From comp.compilers

Related articles
need help with reg. expr., fsa khemani@eden.rutgers.edu (1995-09-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: khemani@eden.rutgers.edu (Maverick)
Keywords: DFA, lex, question
Organization: Rutgers University
Date: Thu, 28 Sep 1995 06:01:17 GMT

hi,


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
fsa.


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
greatly appreciated.


thanks much,
yash
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.