Regex reuse - Revision history

Brianegge: /* When does it makes sense to use a lexer? */

2009-08-05T01:13:07Z

When does it makes sense to use a lexer?

← Older revision		Revision as of 01:13, 5 August 2009
Line 123:		Line 123:
	# More than three capturing groups		# More than three capturing groups
	# Many similar rules		# Many similar rules
	# You start building multiple case/switch statements to keep track of ~~application~~ state. A parser is really just a DSL to create [http://en.wikipedia.org/wiki/Finite-state_machine finite state machines].		# You start building multiple case/switch statements to keep track of parsing state. A parser is really just a DSL to create [http://en.wikipedia.org/wiki/Finite-state_machine finite state machines].
	# You start using multi-line regular expressions		# You start using multi-line regular expressions

Brianegge at 01:02, 5 August 2009

2009-08-05T01:02:02Z

← Older revision		Revision as of 01:02, 5 August 2009
Line 124:		Line 124:
	# Many similar rules		# Many similar rules
	# You start building multiple case/switch statements to keep track of application state. A parser is really just a DSL to create [http://en.wikipedia.org/wiki/Finite-state_machine finite state machines].		# You start building multiple case/switch statements to keep track of application state. A parser is really just a DSL to create [http://en.wikipedia.org/wiki/Finite-state_machine finite state machines].
			# You start using multi-line regular expressions

	Back to [[Parsers Presentation]]		Back to [[Parsers Presentation]]

Brianegge at 01:01, 5 August 2009

2009-08-05T01:01:26Z

← Older revision		Revision as of 01:01, 5 August 2009
Line 126:		Line 126:

	Back to [[Parsers Presentation]]		Back to [[Parsers Presentation]]


			[[Category:Java]]
			[[Category:Parsers]]
			[[Category:Regex]]

Brianegge at 01:00, 5 August 2009

2009-08-05T01:00:41Z

← Older revision		Revision as of 01:00, 5 August 2009
Line 115:		Line 115:
	}		}
	</geshi>		</geshi>

			== When does it makes sense to use a lexer? ==

			Here's some rough guidelines on when to switch from a few regular expressions to a lexer/parser:

			# More than a dozen regular expressions
			# More than three capturing groups
			# Many similar rules
			# You start building multiple case/switch statements to keep track of application state. A parser is really just a DSL to create [http://en.wikipedia.org/wiki/Finite-state_machine finite state machines].

	Back to [[Parsers Presentation]]		Back to [[Parsers Presentation]]

Brianegge at 00:54, 5 August 2009

2009-08-05T00:54:41Z

← Older revision		Revision as of 00:54, 5 August 2009
Line 3:		Line 3:
	When you start your project, you say, this will only a simple regular expression. Your first address is:		When you start your project, you say, this will only a simple regular expression. Your first address is:

	<~~pre~~>		<geshi>
	312 Cox Rd		312 Cox Rd
	Cheyenne, WY 82009		Cheyenne, WY 82009
	</~~pre~~>		</geshi >

	So your write your first expression:		So your write your first expression:
	<~~pre~~>		<geshi>
	(\d+) +(\w+) +(\w+)\n(\w+), (\w+) (\d+)		(\d+) +(\w+) +(\w+)\n(\w+), (\w+) (\d+)
	</~~pre~~>		</geshi >

	This works, but fails on your next address due to an apartment and a two word city.		This works, but fails on your next address due to an apartment and a two word city.

	<~~pre~~>		<geshi>
	270 Marin Blvd Apt 20T		270 Marin Blvd Apt 20T
	Jersey City, NJ 07302		Jersey City, NJ 07302
	</~~pre~~>		</geshi>

	Since Java doesn't support named groups, adding another group is going to break your code. You can use a regex library which does support named groups, you can change your code, or have multiple regular expressions. Let's say you modify the regular expression.		Since Java doesn't support named groups, adding another group is going to break your code. You can use a regex library which does support named groups, you can change your code, or have multiple regular expressions. Let's say you modify the regular expression.

	<~~pre~~>		<geshi>
	^(\d+) +(\w+) +(\w+)( (\w+) (\w+))?\n([\w ]+), (\w+) (\d+)$		^(\d+) +(\w+) +(\w+)( (\w+) (\w+))?\n([\w ]+), (\w+) (\d+)$
	</~~pre~~>		</geshi>

	Again, things go well until you get this address, which has a fraction, a zip+4, and a period of the street type.		Again, things go well until you get this address, which has a fraction, a zip+4, and a period of the street type.
	<~~pre~~>		<geshi>
	93 1/2 E 7th St.		93 1/2 E 7th St.
	New York, NY 10009-5731		New York, NY 10009-5731
	</~~pre~~>		</geshi>

	Just extend the regex a little more...		Just extend the regex a little more...
	<~~pre~~>		<geshi>
	^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (\w+) (\d{5})(-\d{4})?$		^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (\w+) (\d{5})(-\d{4})?$
	</~~pre~~>		</geshi>

	An suppose you want to only accept valid US States and territories....		An suppose you want to only accept valid US States and territories....
	<~~pre~~>		<geshi>
	^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (AL\|AK\|AZ\|AR\|CA\|CO\|CT\|DE\|FL\|GA\|HI\|ID\|IL\|IN\|IA\|KS\|KY\|LA\|ME\|MD\|MA\|MI\|MN\|MS\|MO\|MT\|NE\|NV\|NH\|NJ\|NM\|NY\|NC\|ND\|OH\|OK\|OR\|PA\|RI\|SC\|SD\|TN\|TX\|UT\|VT\|VA\|WA\|WV\|WI\|WY\|AS\|DC\|FM\|GU\|MH\|MP\|PW\|PR\|VI\|AE\|AA\|AE\|AE\|AE\|AP) (\d{5})(-\d{4})?$		^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (AL\|AK\|AZ\|AR\|CA\|CO\|CT\|DE\|FL\|GA\|HI\|ID\|IL\|IN\|IA\|KS\|KY\|LA\|ME\|MD\|MA\|MI\|MN\|MS\|MO\|MT\|NE\|NV\|NH\|NJ\|NM\|NY\|NC\|ND\|OH\|OK\|OR\|PA\|RI\|SC\|SD\|TN\|TX\|UT\|VT\|VA\|WA\|WV\|WI\|WY\|AS\|DC\|FM\|GU\|MH\|MP\|PW\|PR\|VI\|AE\|AA\|AE\|AE\|AE\|AP) (\d{5})(-\d{4})?$
	</~~pre~~>		</geshi>

	Continuing to add more rules to the same regular expression, or adding additional regular expressions to handle all the different cases can soon lead to completely unreadable code. See the [[http://www.regular-expressions.info/email.html RFC822 regex] for an example of a 6000 character long regex expression.		Continuing to add more rules to the same regular expression, or adding additional regular expressions to handle all the different cases can soon lead to completely unreadable code. See the [[http://www.regular-expressions.info/email.html RFC822 regex] for an example of a 6000 character long regex expression.

	Lastly, you must get the data out of the various capturing groups. Identifying where to find the data in the examples 13 groups can be rather tricky. The built in Java regex package doesn't supported named group, but other languages and libraries do. Using numeric groups, your code will look something like:		Lastly, you must get the data out of the various capturing groups. Identifying where to find the data in the examples 13 groups can be rather tricky. The built in Java regex package doesn't supported named group, but other languages and libraries do. Using numeric groups, your code will look something like:
	<~~pre~~>		<geshi>
	address.setStreetNumber(join(matcher.group(1), matcher.group(2)));		address.setStreetNumber(join(matcher.group(1), matcher.group(2)));
	address.setStreetName(join(matcher.group(3), matcher.group(4), matcher.group(5)));		address.setStreetName(join(matcher.group(3), matcher.group(4), matcher.group(5)));
Line 52:		Line 52:
	address.setState(matcher.group(11));		address.setState(matcher.group(11));
	address.setPostcode(matcher.group(12) + matcher.group(13) == null ? "" : ("-" + matcher.group(13)));		address.setPostcode(matcher.group(12) + matcher.group(13) == null ? "" : ("-" + matcher.group(13)));
	</~~pre~~>		</geshi>

	Adding a group another group to the regex means all these group number are going to change.		Adding a group another group to the regex means all these group number are going to change.

			== Lexer Solution ==

			Instead of stringing together more and more regex rules, one can use a lexer to make reusable regex components. Here's the token definitions:

			<geshi lang="java">
			TOKEN :
			{
			< FRACTION : ["1"-"9"] (["0"-"9"])* "/" ["1"-"9"] (["0"-"9"])* >
			\| < CARDINAL : "N" \| "S" \| "E" \| "W" \| "NORTH" \| "SOUTH" \| "EAST" \| "WEST" >
			\| < USSTATE : "AL" \| "AK" \| "AZ" \| "AR" \| "CA" \| "CO" \| "CT" \| "DE" \| "FL" \| "GA" \| "HI" \| "ID" \| "IL" \| "IN" \| "IA" \| "KS"
			\| "KY" \| "LA" \| "ME" \| "MD" \| "MA" \| "MI" \| "MN" \| "MS" \| "MO" \| "MT" \| "NE" \| "NV" \| "NH" \| "NJ" \| "NM" \| "NY" \| "NC" \|
			"ND" \| "OH" \| "OK" \| "OR" \| "PA" \| "RI" \| "SC" \| "SD" \| "TN" \| "TX" \| "UT" \| "VT" \| "VA" \| "WA" \| "WV" \| "WI" \| "WY" \| "AS"
			\| "DC" \| "FM" \| "GU" \| "MH" \| "MP" \| "PW" \| "PR" \| "VI" \| "AE" \| "AA" \| "AE" \| "AE" \| "AE" \| "AP" >
			\| < CANSTATE : "AB" \| "BC" \| "MB" \| "NB" \| "NL" \| "NT" \| "NS" \| "NU" \| "ON" \| "PE" \| "QC" \| "SK" \| "YT" >
			\| < APT : "APT" \| "UNIT" >
			\| < USZIP : (["0"-"9"]){5} ("-" (["0"-"9"]){4} )? >
			\| < CANPOST : ["A"-"Z"] ["0"-"9"] ["A"-"Z"] " " ["0"-"9"] ["A"-"Z"] ["0"-"9"] >
			\| < NUMBER : ["1"-"9"] (["0"-"9"])* >
			\| < WORD : (["0"-"9", "A"-"Z"])+ >
			\| < EOL : "\n" \| "\r" \| "\r\n" >
			}
			</geshi>

			One can then define the productions:

			<geshi lang="java">
			Address parse() :
			{
			Address a = new Address();
			}
			{
			LOOKAHEAD(256)
			usAddress(a) { return a; }
			\| canadaAddress(a) { return a; }
			}
			void usAddress(Address a) :
			{
			a.setCountry("USA");
			}
			{
			streetNumber(a)
			streetName(a)
			streetType(a)
			( apartment(a) )?
			<EOL>
			city(a) (",")?
			state(a)
			zip(a)
			<EOF>
			}
			void zip(Address a) :
			{
			Token z;
			}
			{
			z = <USZIP>
			{ a.setPostcode(z.image); }
			}
			</geshi>

	Back to [[Parsers Presentation]]		Back to [[Parsers Presentation]]

Brianegge at 00:43, 5 August 2009

2009-08-05T00:43:17Z

← Older revision		Revision as of 00:43, 5 August 2009
Line 55:		Line 55:

	Adding a group another group to the regex means all these group number are going to change.		Adding a group another group to the regex means all these group number are going to change.

			Back to [[Parsers Presentation]]

Brianegge at 12:41, 6 June 2007

2007-06-06T12:41:55Z

← Older revision		Revision as of 12:41, 6 June 2007
Line 43:		Line 43:

	Continuing to add more rules to the same regular expression, or adding additional regular expressions to handle all the different cases can soon lead to completely unreadable code. See the [[http://www.regular-expressions.info/email.html RFC822 regex] for an example of a 6000 character long regex expression.		Continuing to add more rules to the same regular expression, or adding additional regular expressions to handle all the different cases can soon lead to completely unreadable code. See the [[http://www.regular-expressions.info/email.html RFC822 regex] for an example of a 6000 character long regex expression.

			Lastly, you must get the data out of the various capturing groups. Identifying where to find the data in the examples 13 groups can be rather tricky. The built in Java regex package doesn't supported named group, but other languages and libraries do. Using numeric groups, your code will look something like:
			<pre>
			address.setStreetNumber(join(matcher.group(1), matcher.group(2)));
			address.setStreetName(join(matcher.group(3), matcher.group(4), matcher.group(5)));
			address.setApartment(matcher.group(9));
			address.setCity(matcher.group(10));
			address.setState(matcher.group(11));
			address.setPostcode(matcher.group(12) + matcher.group(13) == null ? "" : ("-" + matcher.group(13)));
			</pre>

			Adding a group another group to the regex means all these group number are going to change.

Brianegge at 05:31, 3 June 2007

2007-06-03T05:31:21Z

← Older revision		Revision as of 05:31, 3 June 2007
Line 32:		Line 32:
	</pre>		</pre>

	Just ~~extends~~ the regex a little more...		Just extend the regex a little more...
	<pre>		<pre>
	^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (\w+) (\d{5})(-\d{4})?$		^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (\w+) (\d{5})(-\d{4})?$
	</pre>		</pre>

			An suppose you want to only accept valid US States and territories....
			<pre>
			^(\d+( \d/\d)?) +([NSEW] )?(\w+) +(\w+)(.)?( (\w+) (\w+))?\n([\w ]+), (AL\|AK\|AZ\|AR\|CA\|CO\|CT\|DE\|FL\|GA\|HI\|ID\|IL\|IN\|IA\|KS\|KY\|LA\|ME\|MD\|MA\|MI\|MN\|MS\|MO\|MT\|NE\|NV\|NH\|NJ\|NM\|NY\|NC\|ND\|OH\|OK\|OR\|PA\|RI\|SC\|SD\|TN\|TX\|UT\|VT\|VA\|WA\|WV\|WI\|WY\|AS\|DC\|FM\|GU\|MH\|MP\|PW\|PR\|VI\|AE\|AA\|AE\|AE\|AE\|AP) (\d{5})(-\d{4})?$
			</pre>

			Continuing to add more rules to the same regular expression, or adding additional regular expressions to handle all the different cases can soon lead to completely unreadable code. See the [[http://www.regular-expressions.info/email.html RFC822 regex] for an example of a 6000 character long regex expression.

Brianegge at 22:42, 2 June 2007

2007-06-02T22:42:58Z

@@ Line 24: / Line 24: @@
 <pre>
 ^(\d+) +(\w+) +(\w+)( (\w+) (\w+))?\n([\w ]+), (\w+) (\d+)$
 </pre>

Brianegge at 07:32, 2 June 2007

2007-06-02T07:32:29Z

New page

In a project I worked on, thousands of emails were parsed each day, with hundreds of different formats. When a new email would come along which would fail to parse, another regular expression would be added to the Perl program which did the parsing. This soon turned into the most unreadable program one could imagine, and someone needing to tweak it would have no idea where to start. The end solution was to rewrite the app in Python, and use one of Python's lex/yacc tools. Since the described system is encumbered, I'll use the example of needing to parse mailing addresses and stick them into a database. Let's say your an eBay merchant, and people just email you their addresses in any format they choose.

When you start your project, you say, this will only a simple regular expression. Your first address is:

<pre>
312 Cox Rd
Cheyenne, WY 82009
</pre>

So your write your first expression:
<pre>
(\d+) +(\w+) +(\w+)\n(\w+), (\w+) (\d+)
</pre>

This works, but fails on your next address due to an apartment and a two word city.

<pre>
270 Marin Blvd Apt 20T
Jersey City, NJ 07302
</pre>

Since Java doesn't support named groups, adding another group is going to break your code. You can use a regex library which does support named groups, you can change your code, or have multiple regular expressions. Let's say you modify the regular expression.

<pre>
^(\d+) +(\w+) +(\w+)( (\w+) (\w+))?\n([\w ]+), (\w+) (\d+)$
</pre>