Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: RFC: Parsing with perl - Regexes and beyond

by pKai (Priest)
on Apr 03, 2008 at 21:21 UTC ( #678271=note: print w/ replies, xml ) Need Help??


in reply to RFC: Parsing with perl - Regexes and beyond

The first two definitions are recursive, so they are not "regular" any more.

You can argue that the first production is "tail recursive" which does not pose a problem with respect to regularity. Like a tail recursive function can be transformed into a loop.

The non-regularity comes with the 2nd production.

term        -> '(' term ')'

The point is that term can grow to arbitrary length and we still should keep the correspondence between the two parentheses, which is not possible with (CS)-Regexes ("pumping lemma").

This last observation is the border where you need a CFL-parser and would be lost with Regexes alone.


Comment on Re: RFC: Parsing with perl - Regexes and beyond
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://678271]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (8)
As of 2014-09-18 09:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (109 votes), past polls