You are viewing fare

An anonymous user wrote
on March 25th, 2005 at 11:00 pm

Re: parsing

Actually, a CFG can account for balanced parens. CFGs are recognized by nondeterministic pushdown automata. These have stacks. When encountering (, push something onto the stack. When encountering ), pop it.

Remember that a CFG is a grammar with rules of the form Symb -> Symb*. A CFG for an s-expr syntax consisting of only parens and symbols looks like this:
Expr -> Atom | List
List -> ( Expr List_end
List_end -> ) | Expr List_end

I think you're probably thinking of linear grammars, which generate regular languages that are accepted by deterministic finite automata, which have no stack. Those cannot balance a possibly infinite number of parentheses, as their grammars must be finite.

(Read Comments)

No HTML allowed in subject

  
 
   
 

Notice! This user has turned on the option that logs your IP address when posting. 

(will be screened)

eyes black and white

July 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Tags

Powered by LiveJournal.com