2 ms·
Yes, HTML is a deterministic context-free language, so you can parse with a DPDA. In addition, tokens are regular (as it is for many languages), so you can use
by aidenn0 6y ago
Yes, HTML is a deterministic context-free language, so you can parse with a DPDA.
In addition, tokens are regular (as it is for many languages), so you can use a regex for tokenization.
All you need for writing a recursive descent parser with backtracking is a call-stack, so are all LL(k) and most practical CFGs also parseable with regex?
- chubot 6y agoI am not sure if you can say that precisely -- I added the caveats about the rules for end tags, and the rules for stray < and >. But certainly a useful subset of HTML can be parsed with a DPDA. (I'd be interested in more analysis of that; arbitrary tags are another factor) It's a matter of opinion but I would say recursive descent is "nontrivial", whereas matching tags is "trivial". Recursive descent involves some choice around lookahead or backtracking. It can be slow if you do the wrong thing, hard to debug, etc. It takes a little practice, and correspondence with a grammar is important. Whereas matching HTML tags requires no lookahead, and I would say anyone can figure it out just with a simple code reading. Even the "inverted" OOP style is "simple", but annoying for me to read and correctly modify. The call stack reads much better.