adjacence en tant qu'opérateur - est-ce que n'importe quel lexer peut le gérer?

Question

Supposons qu'une langue définisse la contiguïté de deux symboles alphanumériques mathématiques unicodes en tant qu'opérateur. Say, +1 signifie% adj + 1, où% adj représente n'importe quelle adjacence d'opérateur, la multiplication dans ce cas. Je me demandais, est-ce que n'importe quel outil d'analyse lexicale existant peut gérer cela?

Answer 1

Les opérateurs invisibles ne peuvent pas être reconnus avec une analyse lexicale, pour des raisons qui devraient être plus ou moins évidentes. Vous pouvez seulement déduire la présence d'un opérateur invisible en analysant le contexte syntaxique, qui est le rôle d'un analyseur. Bien sûr, la plupart des outils d'analyse lexicale permettent l'exécution de code arbitraire pour chaque jeton reconnu, donc rien ne vous empêche de construire une machine d'état, ou même un analyseur complet, dans l'analyseur lexical. C'est rarement un bon design.

Si votre langage n'est pas ambigu, il n'y a pas de problème pour gérer la contiguïté dans votre grammaire. Mais il faut faire attention. Par exemple, vous voulez rarement x-4 à analyser comme une multiplication des x et -4, mais une grammaire naïve qui comprenait, par exemple.,

expr -> term | expr '-' term 
term -> factor | term factor | term '*' factor 
factor -> ID | NUMBER | '(' expr ')' | '-' factor 

comprendrait cette ambiguïté. Pour le résoudre, vous devez interdire la production de contiguïté avec un second opérande commençant par un opérateur unaire:

expr -> term | expr '-' term 
term -> factor | term item | term '*' factor 
factor -> item | '-' factor 
item -> ID | NUMBER | '(' expr ')' 

Notez la différence entre term -> term '*' factor, qui permet x * - y et term -> term base, qui ne permet pas x - y (expr -> expr '-' term reconnaît x - y comme une soustraction).

Pour des exemples de grammaires sans contexte qui permettent l'adjacence en tant qu'opérateur, voir, par exemple, Awk, dans lequel adjacence représente la concaténation de chaîne, et Haskell, dans lequel il représente l'application de fonction.

---

Puisque cette question se présente de temps en temps, il y a déjà un certain nombre de réponses pertinentes sur SO. En voici quelques-unes:

• Parsing a sequence of expressions using yacc. Opérateur d'application de fonction invisible. Utilise yacc/bison; inclut à la fois des solutions explicites et basées sur la priorité

• yacc - Precedence of a rule with no operator? Opérateur de concaténation de chaîne invisible. Utilise Ply (générateur d'analyseur Python)

• Concatenation shift-reduce conflict Un autre opérateur de concaténation invisible. Utilise JavaCUP.

• Parsing a sequence of expressions using yacc Opérateur d'application de fonction invisible. Utilise fsyacc (générateur d'analyseur F #)

• Using yacc precedence for rules with no terminals, only non-terminals. Adjacence dans les expressions mathématiques ordinaires. Utilise yacc/bison avec des règles de précédence.

• bison/yacc - limits of precedence settings. Haskell-like application application adjacence. Utilise yacc/bison avec des règles de priorité.

Answer 2

Voici un exemple en utilisant pyparsing en Python:

import pyparsing as pp 

integer = pp.pyparsing_common.integer() 
variable = pp.oneOf(list("abcdefghijklmnopqrstuvwxyz")) 

base_operand = integer | variable 

implied_multiplication = pp.Empty().addParseAction(lambda: "*") 
expr = pp.infixNotation(base_operand, 
       [ 
        ("**", 2, pp.opAssoc.LEFT), 
        (implied_multiplication, 2, pp.opAssoc.LEFT), 
        (pp.oneOf("+ -"), 1, pp.opAssoc.RIGHT), 
        (pp.oneOf("* /"), 2, pp.opAssoc.LEFT), 
        (pp.oneOf("+ -"), 2, pp.opAssoc.LEFT), 
       ]) 

Cela suppose que les variables ne sont que des caractères uniques. Il y a aussi un peu de falsification de la préséance des opérations pour faire fonctionner la contiguïté, l'exponentiation et les signes avant-coureurs. L'action d'analyse ajoutée à l'expression implied_multiplication est là pour montrer l'insertion de l'opérateur de multiplication.

Voici quelques sortie de test:

tests = """ 
    x-4 
    ax**2 + bx +c 
    ax**2-bx+c 
    mx+b 
    """ 
expr.runTests(tests, fullDump=False) 

impressions:

x-4 
[['x', '-', 4]] 

ax**2 + bx +c 
[[['a', '*', ['x', '**', 2]], '+', ['b', '*', 'x'], '+', 'c']] 

ax**2-bx+c 
[[['a', '*', ['x', '**', 2]], '-', ['b', '*', 'x'], '+', 'c']] 

mx+b 
[[['m', '*', 'x'], '+', 'b']]