Re: Is XML context-free?

From: Alfred Einstead (whopkins_at_csd.uwm.edu)
Date: 03/16/04


Date: 16 Mar 2004 10:41:21 -0800


"Dan" <addr@host.org> wrote:
> I've read in a number of places that XML is context-free[...]

Programming languages are not context-free since, among other
things, they have to incorporate constraints such as type-matching
conditions or other operator-operand consistency conditions ...
as well as other constraints, such as run-time conditions or
limitations.

Instead, an enveloping context-free syntax is usually stated for
a programming language inside of which the actual language can be
fit. The grammar, which is context-free, overspecifies the language,
and the constraints are then used to filter out all the stuff the
grammar allows for which the language forbids.

This separates out the context-free part of the language from
the context-sensitive part -- which is generally regarded as
good practice (a kind of modular "programming" discipline for
language design).



Relevant Pages

  • Re: Is Python context-sensitive?
    ... I've recently participated in a discussion of whether Python programming ... language is context-sensitive or context-free. ... contains just indentation and an "a" symbol. ...
    (comp.theory)
  • Re: Is Python context-sensitive?
    ... context-free or do we have to take lexer into consideration as well? ... but solely about whether the syntax of the language can ... using a FSA with a stack? ... apply to programming languages used in practise. ...
    (comp.theory)
  • Articles/books that discuss separating the context-free part of a language from the context-
    ... The poster makes the point that most programming languages define a ... context-free core, and then have additional algorithms which run on the parse ... This separates out the context-free part of the language ...
    (comp.compilers)
  • Re: Proof of inherent ambiguity?
    ... > in the context-free language defined by that grammar has more than one ... > parse tree with that grammar. ... I wonder how one can prove inherent ambiguity. ...
    (sci.lang)
  • Re: Proof of inherent ambiguity?
    ... > in the context-free language defined by that grammar has more than one ... > parse tree with that grammar. ... I wonder how one can prove inherent ambiguity. ...
    (comp.theory)