Est-ce que l'expression lambda de C # est LALR (1)?

Question

La question que je souhaite poser est succintly donné dans le titre. Permettez-moi de donner un exemple de la grammaire en question:

identifier_list
    : identifier
    | identifier_list identifier;

lambda_arguments
    : '(' identifier_list ')'
    | identifier;

lambda
    : lambda_arguments '=>' expression

Ensuite, nous ajoutons dans la normal C une expression de grammaire en particulier,

primary_expression
    : '(' expression ')'
    | identifier
    | lambda;

La vraie question est, est-ce la grammaire LALR(1) analysée, c'est à dire, pouvant être analysé par l'analyseur automatique des générateurs? Ou faut-il un roulé à la main ou GLR de l'analyseur? Notez que je souhaite savoir plus précisément à propos de ce paragraphe, pas à le contexte-les mots-clés sensibles des trucs ou tout autre article.

Ce que je pense maintenant, c'est que si l'analyseur voit '(' identifier ')', ce qui est valable analyse, de sorte que si l'analyseur voit identifier, regarde vers l'avenir en ')', il ne sera pas en mesure de décider laquelle arbre d'analyse pour aller vers le bas. Ce pourrait n'être qu'une maj/réduire les conflits, cependant, que je pouvais éliminer par l'attribution arbitraire de priorité (probablement favouriing '(' identifier ')' ).

Edit: en Fait, j'envisage de voler à l'aide de ce paragraphe de la grammaire pour une fonctionnalité similaire dans une nouvelle langue. J'ai déjà anonyme des fonctions similaires à JavaScript en forme grammaticale, mais mes cobayes grince commentaires se plaint qu'ils sont trop verbeux pour de nombreuses utilisations, et a souligné les expressions lambda C# comme une solution idéale. J'ai été préoccupé par une ambiguïté potentielle résultant de cette solution. Donc, vraiment, j'étais seulement intéressé dans ce paragraphe. Les autres trucs comme les génériques et les castes sont des non-questions pour moi.

Les éditions précédentes de ma grammaire sont mécaniquement analysée et je ne veux pas perdre cette propriété, et mon expérience précédente avec une mécanique générateur me dit qu'il est préférable de vérifier d'ici plutôt que d'essayer moi-même. Pour ma roulés à la main analyseur bien sûr, je pourrais tout simplement spécial de cas '(' identifier anticiper un peu plus loin que la normale.

Answer 1

Tout d'abord, un analyseur de la théorie a toujours été un de mes points faibles. Je travaille principalement sur la sémantique des analyseurs.

Deuxièmement, le C# analyseurs qui j'ai travaillé ont été générés par descente récursive des analyseurs. Un de mes anciens collègues qui n'ont une forte expérience dans l'analyseur de la théorie de construire son propre analyseur générateur et de la fed, le C# grammaire en avec succès, mais je ne sais pas quel genre de violations flagrantes des hacks de le faire en découle.

Donc ce que je dis ici est de prendre cette réponse avec la quantité appropriée de scepticisme.

---

Comme vous le notez, les lambdas sont légèrement vexer, parce que vous devez être prudent à ce sujet entre parenthèses de l'expression, il y aurait peut être une mise entre parenthèses de l'expression, un opérateur de cast ou un paramètre lambda liste, et le paramètre lambda liste pourrait être de différentes formes. Mais toutes les choses ont considéré, en ajoutant des lambdas de C# 3.0 a été relativement facile, grammaticalement; le piratage, l'analyseur n'a pas été trop difficile, c'était l'analyse sémantique que c'était un ours pour les lambdas.

Les vrais problèmes épineux dans le C# grammaire aussi loin que le regard va sont génériques et de moulages.

Les génériques ont été ajoutés en C# 2, après la langue déjà eu >>, > et < opérateurs, qui peuvent causer des problèmes bizarres quand vous jetez des génériques dans le mélange.

Le problème classique est évidemment A ( B < C, D > ( E ) ) Ne l'invocation de la méthode de A prennent deux arguments: B < C et D > (E) ou un, B<C,D>( E )?

La règle de lever l'ambiguïté est:

Si une séquence de jetons peut être analysé comme un simple nom, membre d'accès, ou un pointeur-membre d'accès se terminant par un type-liste d'arguments, le jeton immédiatement après la clôture > jeton est examiné. Si c'est de ( ) ] : ; , . ? == != , puis le type d'argument-liste est conservée dans le cadre de la simple nom, membre de l'accès ou du pointeur de membre d'accès et de toute autre possibilité d'analyser de la séquence de jetons est éliminé. Sinon, le type de l'argument-la liste n'est pas considéré comme faisant partie de la simple nom, membre de l'accès ou du pointeur de membre d'accès, même si il n'y a pas d'autre possible d'analyser la séquence de jetons.

Le deuxième problème avec la grammaire remonte à C# 1.0, et c'est l'opérateur de cast. Le problème est qu' (x)-y pourrait signifier "cast -y type x" ou elle pourrait signifier pour soustraire y de x. Ici, la règle est:

Une séquence d'un ou plusieurs jetons entre parenthèses est considéré comme le début de la fonte de l'expression seulement si au moins une des conditions suivantes est vraie:

La séquence de jetons est la grammaire correcte pour un type, mais pas pour une expression.

La séquence de jetons est la grammaire correcte pour un type, et le jeton immédiatement à la suite de la fermeture de parenthèses est le signe "~", le jeton "!", le jeton "(", un identifiant, un littéral, ou n'importe quel mot, sauf as et is.

Les règles qui désambiguïser les deux cas, impliquent potentiellement importants regardez-les recherches en avant dans la théorie, mais dans la pratique vous ont que très rarement en arrière jusqu'à l'analyseur de très loin.

Answer 2

Une expression de la grammaire augmentée avec C#-style lambdas n'est pas LALR(1), mais c'est probablement LALR(2). Par conséquent, il est possible (mais pas forcément triviale) pour produire un équivalent LALR(1) grammaire: voir modifier ci-dessous.

Vous allez obtenir un réduire/réduire les conflits sur l'entrée:

( id )

parce qu' id peut être réduit à identifier_list ou expression (indirectement, dans le second cas), et l'analyseur ne peut pas dire laquelle est la bonne basée sur une anticipation de jeton ()).

Il pourrait dire basé sur deux d'anticipation des jetons, depuis l' identifier_list de réduction n'est possible que si le second jeton est - =>, et tant qu' => n'est pas un opérateur dans votre langue, l' expression de réduction n'est pas possible si le second jeton est - =>. Donc, je pense que c'est probablement LALR(2), bien que je ne peux pas dire avec certitude.

Le cas où il n'y a plus d'un identificateur n'est pas problématique, puisque, dans

( id1 id2 )

id1 id2 ne peut pas être réduite à une expression (en plus de l'expression des langues; le vôtre, bien sûr, différent). Le cas où un seul sans parenthèse identificateur est immédiatement suivie par => est également pas de problèmes, pour autant que `=>' n'est pas valide d'opérateur.

Modifier

J'ai oublié de préciser dans ma réponse originale à cette question qu'il n'y a pas une telle chose comme un LALR(2) de la langue. Le langage reconnu par un LALR(2) la grammaire est également reconnu par certains LALR(1) de la grammaire. En fait, il est constructif de la preuve de cette assertion, qui permet à la mécanique de la création d'un tel LALR(1) de la grammaire, avec une procédure pour récupérer l'original de l'arbre d'analyse.

Dans ce cas, c'est encore plus simple pour générer un LALR(1) de la grammaire, puisque, comme mentionné ci-dessus il y a seulement une production qui exige plus d'anticipation. La solution est de retarder la réduction par un jeton. En d'autres termes, à l'origine, la grammaire comprend quelque chose comme:

primary:           '(' expression ')'
lambda_parameters: '(' id_list ')'

où les deux id_list et expression dériver le terminal ID. Hormis ID, les dérives de ces deux non-terminaux sont disjoints, afin que nous puissions résoudre le problème comme suit:

primary:           '(' expression_not_id ')'
       |           '(' ID ')'


lambda_parameters: '(' id_list_not_id ')'
                 | '(' ID ')' "

Il ne reste plus qu'à diviser les productions expression et id_list , de manière à séparer l' ID de cas, qui s'avère ne pas être très difficile. Ci-dessous est un exemple simplifié, qui pourrait être facilement étendu; il est limité à l'addition, la multiplication et la fonction de l'application (que j'ai inclus pour montrer que les deux séparées par des virgules, les listes ne sont pas un problème):

%token ID LITERAL RIGHT_ARROW
%start expr
%%
primary: primary_not_id | ID ;
term:    term_not_id    | ID ;
sum:     sum_not_id     | ID ;
expr:    expr_not_id    | ID ;

expr_list: expr         | expr_list ',' expr ;
arguments: '(' ')'      | '(' expr_list ')' ;

ids: ID ',' ID          | ids ',' ID ;
parameters: '(' ID ')'  | '(' ids ')' ;

primary_not_id: LITERAL
              | '(' expr_not_id ')'
              | '(' ID ')'
              | primary arguments
              ;

term_not_id: primary_not_id
           | term '*' primary
           ;

sum_not_id: term_not_id
          | sum '+' term
          ;

expr_not_id: sum_not_id
           | parameters RIGHT_ARROW expr
           ;

Remarque: La grammaire dans l'OP produit lambdas avec plusieurs paramètres comme une séquence d'identificateurs ne sont pas séparées par des virgules: (a b) => a + b. Je pense que la véritable intention était d'utiliser des virgules: (a, b) => a + b, et c'est ce que j'ai fait au-dessus de la grammaire. La différence est importante si votre langue a un opérateur virgule, comme le C de la famille, parce que dans ce cas, une expression peut-être '(' expression_list ')', ce qui entre en conflit avec un lambda de la liste des paramètres. Un naïf mise en œuvre entraînerait dans un à réduire/réduire les conflits sur le premier expression dans la expression_list qui ne peut pas être résolu avec une anticipation, depuis l' expression_list pourrait être arbitrairement longue.

Il y a une solution pour ce cas aussi, cependant: cela consiste à séparer id_list de expression_list, quelque chose comme ce qui suit:

id_list:         ID
       |         id_list ',' ID
       ;
expression_list_not_id_list: expression_not_id
                           | id_list ',' expression_not_id
                           | expression_list_not_id_list ',' expression
                           ;
expression_list: expression_list_not_id_list
               | id_list
               ;

Je ne voulais pas faire un plein de grammaire, mais, depuis, je n'ai aucune idée de ce que la langue cible exige.

Answer 3

Oui, cette situation est un simple de réduire/réduire les conflits.

%token identifier ARROW

%%

program
: expression
| program expression
;

identifier_list
: identifier
| identifier_list identifier;

lambda_arguments
: '(' identifier_list ')'
| identifier;

lambda
: lambda_arguments ARROW expression;

primary_expression
: '(' expression ')'
| identifier
| lambda;


expression : primary_expression


$ yacc -v test.6.y 
conflicts: 1 reduce/reduce

C'est exactement de ne pas savoir qui de réduction à faire lors de la prochaine symbole ): sommes-nous à la réduction d'un lambda_arguments liste ou un primary_expression?

L'analyseur générateur a résolu dans le mauvais sens, en favorisant le lambda de la liste. Mais cela signifie qu'une mise entre parenthèses de l'expression ne peut pas être produit.

Il y a plusieurs façons de sortir de ce gâchis. Ici est probablement l'approche la plus simple, une modification de la grammaire qui ne contient pas de conflits:

%token identifier ARROW

%%

program
: expression
| program expression
;

identifier_list
: identifier
| identifier_list identifier
;

lambda_arguments
: '(' identifier identifier_list ')'
| identifier
;

primary_expression
: '(' expression ')'
| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression
| identifier
;

expression : primary_expression

Nous plier le lambda de la syntaxe en primary_expression, et lambda_arguments est désormais soit un seul sans parenthèse identificateur, ou une liste d'au moins deux identifiants.

En outre, il y a deux syntaxique cas maintenant pour les lambdas:

| '(' expression ')' ARROW expression
| lambda_arguments ARROW expression

Donc, de deux sémantique de l'action, les règles doivent être écrites. La logique commune, de sorte qu'il peut être cultivé à une fonction d'assistance qui construit l'arbre de syntaxe nœud pour un lambda.

L'action pour la première variante syntaxique a pour inspecter l' $2 de la main droite d'un symbole, et vérifier que c'est une simple expression primaire constitué d'un identifiant du jeton. Si c'est le cas, l'action des fissures d'ouvrir l'expression, prend l'identifiant et construit un lambda de la liste de cet identifiant, et utilise cette liste pour générer le lambda syntaxique nœud qui se termine par la règle de l'output ( $$ de la valeur, en Yacc termes). Si $2 est tout autre type d'expression, un diagnostic est émis: il est mauvais lambda syntaxe, comme ( 2 + 2 ) => foo. Bien sûr, cela a été accepté par l'analyseur, ce qui est la règle obtenu invoquée. Mais il est maintenant du point de vue sémantique rejeté (où du point de vue sémantique fait référence à une faible teneur en calories version du mot "sémantique").

L'action de la deuxième variante est simple: prendre le lambda de la liste, l'expression corporelle et de faire un lambda nœud, comme avant.

Il suffit de mettre, le lambda de la syntaxe est si bien intégré dans la syntaxe de l'expression, qu'il ne peut pas être facilement cultivé en séparer complètement les règles qui sont portées par une même production que les appels d' lambda d'être réduite à primary_expression. C'est un vœu pieux, car les règles pour une maj de réduire l'analyseur ne sont pas des appels de fonction.

Answer 4

Je ne pense pas que le lambda-expression de la grammaire question est intéressante par elle-même, sauf si l'on connaît le reste de la langue est LALR(1).

Si vous voulez connaître la réponse, nourrir votre subgrammar à un LALR(1) analyseur le générateur. Si elle se plaint de décalage de la réduire ou de les réduire-de réduire les conflits, il n'est pas LALR(1). Si une grammaire est LALR(1) est décidée par le fait que vous pouvez construire la transition tables pour elle, par définition.

Souvent on veut un analyseur syntaxique pour l'ensemble de la langue.

Il y a deux questions intéressantes ici.

1) Est C# 4.5 comme une langue LALR(1) à tous? (par exemple, est-il certains grammaire LALR(1)? Notez qu'une grammaire particulière de ne pas être LALR(1) ne signifie pas qu'il n'y a pas un autre.

2) est-ce que le C# grammaires publiées par Microsoft (dans ses multiples formes) LALR(1)?

Je pense que Eric nous a dit que 1) ce n'est pas vrai. Que suggère 2) n'est pas vrai, trop.

C++ nécessite infini d'anticipation pour résoudre ses modèles, en grande partie causée par la localement des possibilités de ">" être interprétée comme un "modèle de fin args" ou "plus grand que". Depuis C# copié ce, je m'attends à avoir un infini d'anticipation des exigences sur le modèle de résolution de trop. Ce n'est certainement pas LALR(1). [Il ya un supplément de mess quant à savoir si ">>" peut être considéré comme un opérateur de décalage, et "> >" ne peut pas, que vous ne pouvez pas fixer dans la grammaire car il ne peut pas voir de l'espace.]

Mon entreprise utilise GLR pour ses outils de traitement du langage, et nous avons un C# 4.5 grammaire qui fonctionne très bien. GLR signifie que nous n'avons pas à penser à la façon de convertir un contexte de grammaire à un LALR(1) compatible (par exemple, plier, tordre, gauche/droite facteur aléatoire), ou un code ad hoc look recherches en avant, etc. et ainsi, nous pouvons nous concentrer sur les problèmes de traitement du code, pas de l'analyse.

Cela signifie que des moulages et autres constructions de produire de l'ambigu des arbres au moment de l'analyse, mais ceux-ci sont facilement résolus si vous avez un type d'information.