Question concerning this list [WebCrawler]

Diez B. Roggisch deets at nospam.web.de
Mon Jan 1 21:08:51 CET 2007


Thomas Ploch schrieb:
> John Nagle schrieb:
>>     Very true.  HTML is LALR(0), that is, you can parse it without
>> looking ahead.  Parsers for LALR(0) languages are easy, and
>> work by repeatedly getting the next character and using that to
>> drive a single state machine.  The first character-level parser
>> yields tokens, which are then processed by a grammar-level parser.
>> Any compiler book will cover this.
>>
>>     Using regular expressions for LALR(0) parsing is a vice inherited
>> >from Perl, in which regular expressions are easy and "get next
>> character from string" is unreasonably expensive.  In Python, at least
>> you can index through a string.
>>
>> 				John Nagle
> 
> I take it with LALR(0) you mean that HTML is a language created by a
> Chomsky-0 (regular language) Grammar?

Nope.

LALR is a context free grammar parsing technique.

Regular expressions can't express languages like

a^n b^n

but something like

<div><div></div></div>

is <div>^2</div>^2

Diez



More information about the Python-list mailing list