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

September 2014

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
282930    

Tags

Powered by LiveJournal.com