Menu
Reading some related questions made me think about the theoretical nature of HTML.
I'm not talking about XHTML-like code here. I'm talking about stuff like this crazy piece of markup, which is perfectly valid HTML(!)
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN"> <html<head> <title// <p ltr<span id=p></span</p> </> So given the enormous complexity that SGML injects here, is HTML a context-free language? Is it a formal language anyway? With a grammar?
What about HTML5?
I'm new to the concept of formal languages, so please bear with me. And yes, I have read the wikipedia article ;)
211
No, JavaScript is not a context-free language. It is very close to one, and the ECMAScript 5 specification does indeed use a context-free grammar1 to describe the language's syntax (you can find all productions in Annex A).
Definition of context-free : of, relating to, or being a grammar or language based on rules that describe a change in a string without reference to elements not in the string also : being such a rule.
Since regular languages are a subset of context-free languages, all programs of bounded size are context-free.
Python is not context free. I've mentioned that most programming languages are not context-free languages. Let's take Python as a first example. The standard way to show that a language is not context free is to use Ogden's Lemma.
Context Free is a concept from language theory that has important implications in parser implementation. A Context Free Language can be described by a Context Free Grammar, which is one in which all rules have a single non-terminal symbol at the left of the arrow:
X→δ That simple restriction allows X to be substituted by the right-hand side of the rules in which appears on the left without regard to what came before or after. For example, if while deriving or parsing one arrives at:
αXλ one is sure that
αδλ is also valid. Examples of non-context-free rules would be:
XY→δ Xa→δ aX→δ Those would require knowing what could be derive arround X to determine if a rule applies, and that leads to non-determinism (what's around X would also like to know what it derives to), which is a no-no in parsing, and in any case we want a language to be well-defined.
The only way to prove that a language is context-free is by proving that there's a context-free grammar for it, which is not an easy task. Most programming languages one comes about are already described by CFGs, so the job is done. But there are other languages, including programming languages, that are described using logic or plain English, so work is required to find if they are context-free.
For HTML, the answer about its context-freedom is yes. SGML is a well defined Context Free Language, and HTML defined on top of it is also a CFL. Parsers and grammars for both languages abound on the Web. At any rate, that there exist LL(k) grammars for valid HTML is enough proof that the language is context-free, because LL is a proven subset of CF.
But the way HTML evolved over the life of the Web forced browsers to treat it as not that well defined. Modern Web browsers will go out of their way to try to render something sensible out of almost anything they find. The grammars they use are not CFGs, and the parsers are far more complex than the ones required for SGML/HTML.
HTML is defined at several levels.
<tags> that define a hierarchical document structure. You can use XML or something XML-like for any purpose, like Apache Ant does for build scripts.The syntactic part is defined well enough that it can be verified. The semantic part is much larger than the syntactic one, and is defined in terms of browser actions regarding HTTP, and the Document Object Model (DOM), and how a model should be rendered to the screen.
In the end:
117
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
