2
$\begingroup$

Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for example, supposed to be included in the language Fortress (now a dead project).

Lexing and parsing such a language seems to me like it would be difficult within the usual lexer-parser framework. In a computer language, unlike human math notation, we want to have variable names that are more than one letter. So if we need to lex the string xyz, we have a problem, because this could, e.g., mean x*yz if x and yz are variables, but it could also mean xy*z if xy and z are variables. The lexer normally wouldn't have this type of information available, so it would have no way of resolving the ambiguity.

Are there ways of reducing this problem to a more standard form that can be handled by a traditional lexer-parser pair, or does it require qualitatively different techniques?

$\endgroup$
3
$\begingroup$

There is no issue parsing a language which uses juxtaposition as an operator provided that it is possible to identify lexical tokens. For example, awk uses juxtaposition for string concatenation, and the following expressions are completely valid:

last_name", "first_name
last_name ", " first_name
last_name comma space first_name

However, two juxtaposed variables must be separated by whitespace to satisfy the lexical constraint. Whitespace is also used to resolve the ambiguity:

last_name(", ")

which might be a function call or a concatenation. Since awk does not require function definitions to precede use of the function, it cannot disambiguate based on the type of last_name; instead, it specifies that a function call cannot have whitespace between the function's name and the (, so that the above is a function call, while:

last_name (", ")

is concatenation.

Fortress's syntax has (or had) a number of other issues which are harder to solve with a simple yacc/lex parser; if I recall correctly, the proof-of-concept implementation used a packrat parser. For example, the syntax allows the use of vertical bars either as operators or as brackets, so |a| might be the absolute value of a. Somewhat complicated whitespace rules were used to disambiguate, and there are other situations in which whitespace is significant, affecting operator precedence. In my opinion, the apparent convenience of having a language which resembles mathematics is out-weighed by the possibility of an unintended parse changing the semantics of the program without any indication as a warning or error. (This sort of issue plagues some more conventional languages also.)

Another class of languages in which juxtaposition is common are unit-aware languages (or calculators), such as GNU Units or Frink. As far as I know neither of these requires any special parsing technology, although there is a general issue with the solidus (/) which can require careful juggling of operator precedence. It's clear what:

2 cm/sec

means. But what about the following:

2/3 cm/sec
2 cm/3 sec
2 g/cm sec^2

(It's relevant that SI insists on parentheses and prohibits multiple solidus symbols, so that the last value must be written as 2 g/(cm sec2); neither 2 g/cm sec2 nor 2 g/cm/sec2 are correct.)

Again, this is not so much a parsing issue as a user interface design problem.

$\endgroup$
4
$\begingroup$

Juxtaposition is used in mathematics because most mathematical texts use single character variables (possibly with diacritic signs, subscripts, superscripts, etc...) so that there is no ambiguity.

A mathematician might write $2x$ to multiply $2$ and $x$. It would be quite unusual to write $x2$ to multiply $x$ by $2$. Actually, as much as I can see (but I am open to contrary examples) a numerical factor always comes first in the product. This unstated rule implies that one never has two numerical factors in succession, which would make it difficult to interpret $22$, which could be $2\times 2$ or the single number $22$. Of course, if two numerical factors in a row were to be acceptable, they would be separated by a space to avoid ambiguity.

Regarding variables, the same has to be true. Several variables can be factors of a product (well, a sequence of products). Either you have a rule that all variables are 1 letter (a constraint that cannot be imposed on numbers), or you maust have a way to separate the variables, either by a space, or by a $\times$ sign.

First I would point out that this is a pure lexer problem: how do I determine what variables are juxtaposed as the factors of a product. The fact that the operator are omitted is not really an issue for the parser (though it may call for some appropriate techniques depending on other syntactic aspects of the language, and the way they interact with the feature we are discussing).

Of course, you can start playing games, like the following which you seem to be actually suggesting. Since all variables are supposed to be declared (that is also true in mathematics), you could juxtapose variables arbitrarily, without spaces, to form a product, and rely on the lexer to determine how to cut the string so that each cut out substring is a declared variable. Of course, depending on what variables you have declared, this can have an ambiguous result (as you suggest in your question), and produce a lattice of variables instead of a sequence of variables.

I created the expression "lattice of variables" after the expression "word lattice" used in speech recognition for exactly the same problem in a different setting. For example, given that you have declared the seven variables: a b c d ab bc cd. Then the string abcd can be cut into several sequences of variables, that can be represented by a loopless finite state automaton like the following (which is what is called a word lattice in speech processing).

     /--- ab ---\
    /            \
    --- a --- b --\--cd --------\
-- /     \                       > -----
   \      \-- bc ------/--- d --/
    \                 /
     \-- ab --- c ---/

Creating this lattice is not difficult, using finite state techniques, when the available variables are known. It would however probably require some changes in standard lexers, as they usually identify lexical element with simpler techniques, simpler use of context.

One way to do it is for the lexer to first identify the string as an expression. It could then call a routine that would access the current symbol table to find relevant identifiers and organise them as a trie to cut the string into existing identifiers. Assuming no ambiguity, the lexer could then give the successive identifiers to the parser, interspersed with $\times$ symbols. So it is rather easy to integrate into existing architectures.

To limit the ambiguity, one can first eliminates by type checking all variables with a type incompatible with use as factor in a product. Or possibly, if there are different kinds of products requiring compatible types, this can be used to eliminate inconsistant sequences of variables.

Remaining ambiguities would probably no be a major problem for the parser (possibly depending on parsing techniques, typing ...). But of course, the ambiguity has to be resolved at some point, if the language is supposed to convey only one meaning.

One way to do it could be to notify an error whenever such an ambiguity is found, with some details about the ambiguity, thus requesting the user to disambiguate by adding a space or a $\times$ symbol.

Though this can be handled technically, I do not think I would recommend it in a language. Even if unambiguous, this is not extremely readable, notwithstanding the fact that the ancient languages such as Latin and Greek used to be written that way.

An alternative could be to accept this kind of notation only with the usual constraints (in mathematics) that I stated above: number must be first and variables must have a single letter for implicit product. But ambiguity could remain between a single variable $xx$ and the product $x\times x$ written without the $\times$ symbol. I guess it would not be very hard, with standard technology.

I think I have exhausted my imagination on this topic. It is not technically difficult, for what I can see. But why would all this be worth the trouble?

$\endgroup$
  • $\begingroup$ But why would all this be worth the trouble? The designers of Fortress seem to have wanted their code to look as much as possible like human math notation, so that sophisticated human users wouldn't have to mentally translate when reading and writing code. My own reason for being interested in the problem is an application designed for unsophisticated users, who would have a hard time translating. I have a hand-written parser that does essentially what your answer described, but it's complicated and not as easy to maintain and extend as a flex-yacc setup might be. $\endgroup$ – Ben Crowell Jul 15 '14 at 3:10
  • $\begingroup$ @BenCrowell I have not looked at Lex and Yacc for a very long time, and would not really know precisely what they cannot do, especially today (and specific tools are off topic here anyway). They belong to a technology family that is usually brutal with ambiguity, which is not what you want. But they are also flexible, and might handle well anything unambiguous you design. Regarding Fortress, the intent was to have several different syntaxes (stylesheets, whatever this is intended to mean for them) for the same language. My guess is that this was a minor gadget. $\endgroup$ – babou Jul 15 '14 at 8:22
  • $\begingroup$ @BenCrowell Regarding your hand written parser, my own feeling is that it is easier to write a parser generator, even when it is to be used only once. I would never trust a hand written parser for anything but a toy language. Another possibility is to make simple changes to Lex, which you would have to maintain, following the architecture I suggest in the answer: call a separate routine to do the cutting. There may still be problems of keyword ambiguity if you have two identifiers "th" and "en", which juxtaposed would be confused with the word "then". $\endgroup$ – babou Jul 15 '14 at 8:24
  • $\begingroup$ @BenCrowell More recent parsers and lexer, intended to handle ambiguity, as often used in natural language processing, might provide a solution. They may not be as polished as Yacc and Lex. Still, this juxtaposition business seems to be a very minor point of mathematical notation. How is the rest handled? That might be a clue to what is to be done. $\endgroup$ – babou Jul 15 '14 at 8:25
  • 1
    $\begingroup$ @BenCrowell PS. I had not read Fortress about pseudo-code analysis. This may be an interesting problem. But, given the informality of it, it is close to natural language processing, allowing ambiguities resolved by contextual (semantics) understanding. This is not in the Lex-Yacc bag of tricks. You should look for general context-free parsers, that can provide multiple analyses (parse forest), and postpone ambiguity resolution to semantics, or asking the user. I am not sure what are the best tools on shelf right now (designers oversell). It also depends on the global design of your project. $\endgroup$ – babou Jul 15 '14 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.