xsl-list
[Top] [All Lists]

Re: [xsl] Are XPath expressions parsed using compiler parsing techniques?

2022-05-08 17:00:48
Hi Roger,

An XPath expression is a query. Not against a database, but against an
XML document.
Are XPath expressions parsed using compiler parsing algorithms?


Even if a query is "interpreted", it is still initially compiled into some
internal form. The answers to the remaining 2 questions largely depend on
each individual implementation of a particular XPath engine.

Anyway, the set of grammar (BNF) rules in the XPath specification is the
actual definition of the language (on a syntax level). Any string that is
processed as input by the XPath engine, that cannot be parsed using the set
of grammar rules presented in the specification, is not an XPath expression
and should not be "interpreted" furter.

As the spec doesn't provide any other obvious way to determine which input
strings are XPath expressions and which are not, it would be logical to
conclude that any such input string is parsed using this set of grammar
rules.

As for whether " XPath expressions are  parsed using compiler parsing
algorithms", whatever algorithm is used for parsing, must still be a
grammar-parsing algorithm, but it would feel unnatural and would need
special justification not to use such well-known and having
widely-available (easy to implement) implementations as LR-1 parsing
techniques or similar.

Is a syntax tree constructed for an XPath expression? Is the syntax tree
traversed?

If we agree with the above, something must be produced as result of the
parsing. It is only natural to organize the parsed representation of the
input XPath expression as a tree, due to the (usual) recursiveness of the
language definition.

This tree will at least correspond to some extent to the grammar rules
whose reductions constitute the parse, Depending on the actual goals of the
processor (like what actions we want to perform on the parse result) , one
may choose the level of detail and group a subtree of fine-grain rules into
just one node that corresponds to the LHS of the rule that is their common
ancestor.

If the result is still a tree (which besides the most simplistic cases it
is), this tree, of course, needs to be interpreted (traversed) in order for
the appropriate actions to be determined and carried out.

Of course, some languages (such as arithmetic expressions) allow an action
to be performed as soon as a grammar rule is reduced, not waiting for the
complete parsing tree to be produced. For example in the following
expression

3 *(5+7)

5 + 7 can be computed as soon as the rule that "5 + 7" is an expression is
recognized.

As we see, how to react to parsed results is a long topic to discuss and
there could exist many different interpretation strategies, depending on
the goals of the language processor.

Thanks,
Dimitre

On Sun, May 8, 2022 at 2:19 PM Roger L Costello costello(_at_)mitre(_dot_)org <
xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:

Hi Folks,

I dug out my old compiler "Dragon book" and started rereading it.

Chapter 1 lists some of the tools that employ compiler techniques. This
one caught my attention:

Query interpreters: A query interpreter translates a predicate containing
relational and boolean operators into commands to search a database of
records satisfying that predicate.

An XPath expression is a query. Not against a database, but against an XML
document. Are XPath expressions parsed using compiler parsing algorithms?
Is a syntax tree constructed for an XPath expression? Is the syntax tree
traversed?

/Roger




-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
To achieve the impossible dream, try going to sleep.
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
Typing monkeys will write all Shakespeare's works in 200yrs.Will they write
all patents, too? :)
-------------------------------------
Sanity is madness put to good use.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--
<Prev in Thread] Current Thread [Next in Thread>