Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can the shunting yard algorithm parse POSIX regular expressions?

At first glance, the shunting yard algorithm seems applicable to POSIX regular expression parsing, but since I don't have much experience (or theoretical background) in writing parsers, I'd like to ask SO before jumping in and writing something only to get stuck halfway.

Perhaps a more sophisticated version of the question is: What is a good formal statement of the class of problems the shunting yard algorithm can be applied to?

Clarification: This question is about whether you can parse POSIX re syntax into an abstract syntax tree using the basic principles of the shunting algorithm, not whether you can use regular expressions to implement the shunting algorithm. Sorry I wasn't clear enough stating that to begin with!

like image 210
R.. GitHub STOP HELPING ICE Avatar asked Nov 12 '10 04:11

R.. GitHub STOP HELPING ICE


2 Answers

I'm fairly sure it can. If you look at Henry Spencer's regular expression package:

regexp.shar.Z

which was the basis for Perl's regular expressions, you will notice that he describes the program as being in "railroad normal form".

like image 91
Martin Broadhurst Avatar answered Sep 21 '22 10:09

Martin Broadhurst


I reckon you'd have some problems because different characters have different meanings in different contexts e.g.

^[^a-z][asd-]

The ^ has two different meanings and so does the -. I think I'd choose a recursive descent parser.

like image 33
JeremyP Avatar answered Sep 22 '22 10:09

JeremyP