Re: Why Chomsky Type 3 grammars are called "Regular"?

valentin tihomirov <spam@abelectron.com> wrote:
>> Regular expressions _alone_ can not describe _all_ type-2 languages.
>
>...In my opinion, any stream of symbols is
>always RE even if it contains no regularities (like ABC), so please explain,
>which rules cannot be described with REs?


Consider:


expression = number | expression "+" number | "(" expression ")"


The first recursion can be converted to a Kleene "*" operator, but the
second can't be -- a finite regular expression can't match balanced
parentheses (and only balanced parentheses) to an arbitrary nesting depth.
--
"Think outside the box -- the box isn't our friend." | Henry Spencer
                                                                -- George Herbert | henry@spsystems.net

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