[JAVA] "Chaîne de caractères parentaux" Résumé de l'exemple d'implémentation d'un analyseur simple

Quel type d'analyseur est qu'il effectue un traitement comme l'exemple d'exécution Python suivant.

>>> p_syn(p_lex(input()))
((10 + 20)*(30 - 40))
[['10', '+', '20'], '*', ['30', '-', '40']]

>>> p_syn(p_lex(input()))
{ "color": [ "red", "green" ] }
[['color'], ':', [['red'], ',', ['green']]]

Nous sommes en train de créer un analyseur simple de type S dans divers langages de programmation avec diverses raisons. N'est-ce pas aussi? Tout en remarquant cela, j'ai décidé de rassembler un exemple de description qui peut être facilement implémenté à la fois pour l'analyseur JSON, l'analyseur de type S ou l'analyseur de la représentation de la structure de données d'origine basée sur des parenthèses, avec une petite modification et un traitement supplémentaire. Analyse des phrases + [Résumé] Syntaxe Tree](https://ja.wikipedia.org/wiki/%E6%8A%BD%E8%B1%A1%E6%A7%8B%E6%96%87%E6%9C%A8) Generation Ainsi, il peut être possible de détourner uniquement la partie d'analyse de la phrase ou uniquement la partie de génération d'arbre de syntaxe abstraite.

spécification

Fonction p_lex (partie analyse de phrase)

A partir de la chaîne de caractères d'entrée, un tableau de chaînes de caractères est généré en utilisant () [] {}", ʻen tant que phrase et vide` en tant que délimiteur.

[Exemple] {(10 + 20) * (30 -40)}['{', '(', '10', '+', '20', ')', '*', '(', '30', '-', '40', ')', '}']

Si vous voulez l'utiliser comme exemple d'un soi-disant programme de calculatrice, vous pouvez également reconnaître des opérateurs tels que + -`` * `/ ʻas expressions.

Fonction p_syn (générateur d'arbre de syntaxe abstraite)

Génère une liste de groupes () [] {}" à partir du tableau de chaînes de caractères ci-dessus.

[Exemple] ['{', '(', '10', '+', '20', ')', '*', '(', '30', '-', '40', ' ) ','} '] [['10', '+', '20'], '*', ['30', '-', '40']]

, : . Etc. restent des éléments de liste, donc selon le but du détournement,, sera supprimé, et ʻA: B et ʻA. B seront une liste de clés et de valeurs. , Etc. peut être requis. De plus, si vous souhaitez modifier le traitement en fonction du type de parenthèse, vous devrez effectuer quelques ajustements.

Autre

Exemple d'implémentation Python

Une partie considérable est détournée de tokenize et read_from_tokens de " lis.py "de Peter Norvig. La description a été modifiée sans utiliser «pop» et «append» pour faciliter la comparaison avec des exemples d'implémentation dans d'autres langues.

p_lex.py


def p_lex(p):
    for s in '()[]{}",':
        p = p.replace(s, ' ' + s + ' ')
    return p.split()

p_syn.py


def p_syn(p):
    t = p[0]
    del p[0]
    if t in '({["':
        r = []
        while p[0] != ')}]"'['({["'.find(t)]:
            r += [p_syn(p)]
        del p[0]
        return (r)
    else:
        return t
>>> p_syn(p_lex(input()))
{"a": [100, f], "b": {"a": [t, "c"], "b": "d"}}
[['a'], ':', ['100', ',', 'f'], ',', ['b'], ':', [['a'], ':', ['t', ',', ['c']], ',', ['b'], ':', ['d']]]

Exemple d'implémentation du langage C

Créé en utilisant la version Python comme modèle. La section d'analyse des phrases utilise «strtok». Dans la partie de génération d'arbre de syntaxe abstraite, une structure de liste est générée par un arbre dichotomisé selon notre passe-temps (?). Pour cette raison, p_syn scanne le tableau de chaînes de caractères par derrière.

p_lex.h


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef P_LEX_H_
#define P_LEX_H_

#define SSTR_MAX 256

int p_lex(const char *p, char* pl[]);

#endif

p_lex.c


#include "p_lex.h"

int p_lex(const char *p, char* pl[])
{
  char pf[SSTR_MAX * 3];
  int i, j = 0;
  for (i = 0; i < strlen(p); i++) {
    switch (p[i]) {
      case '(':
      case ')':
      case '[':
      case ']':
      case '{':
      case '}':
      case '"':
      case ',':
        pf[j++] = ' '; pf[j++] = p[i]; pf[j++] = ' ';
        break;
      case '\n': j++; break;
      default: pf[j++] = p[i];
    }
  }
  pf[j] = '\0';

  char *t;
  int len = 0;
  for (t = strtok(pf, " "); t != NULL; t = strtok(NULL, " "))
    pl[len++] = t;
  pl[len] = NULL;

  return (len);
}

p_syn.h


#include <stdio.h>
#include <stdlib.h>

#ifndef P_SYN_H_
#define P_SYN_H_

typedef unsigned int value_t;
enum NODE_TAG { NODE_STRG, NODE_BTRE };

typedef struct _node_t_ {
  value_t value;
  enum NODE_TAG tag;
} _node_t, *node_t;

node_t node(value_t value, enum NODE_TAG tag);

typedef struct _btree_t_ {
  node_t x;
  node_t y;
} _btree_t, *btree_t;

node_t btree(node_t x, node_t y);

#define str_to_node(p)  (node((value_t)(p), NODE_STRG))
#define node_to_str(p)  ((char *)(p->value))

#define bt_x(p)  (((btree_t)(p->value))->x)
#define bt_y(p)  (((btree_t)(p->value))->y)
#define n_str(p) (p->tag == NODE_STRG)
#define n_btr(p) (p->tag == NODE_BTRE)

node_t p_syn(char *p[], int *pos);

#endif

p_syn.c


#include "p_syn.h"

node_t node(value_t value, enum NODE_TAG tag)
{
  node_t n = (node_t)malloc(sizeof(_node_t));
  n->value = value; n->tag = tag;
  return (n);
}

node_t btree(node_t x, node_t y)
{
  btree_t c = (btree_t)malloc(sizeof(_btree_t));
  c->x = x; c->y = y;
  node_t n = node((value_t)c, NODE_BTRE);
  return (n);
}

char p_syn_rp(char lp)
{
  switch (lp) {
    case ')': return '(';
    case ']': return '[';
    case '}': return '{';
    case '"': return '"';
    default: return '\0';
  }
}

node_t p_syn(char *p[], int *pos)
{
  char *t = p[*pos];
  *pos = *pos - 1;

  switch (t[0]) {
    case ')':
    case ']':
    case '}':
    case '"': {
      node_t r = NULL;
      while (p[*pos][0] != p_syn_rp(t[0])) {
        r = btree(p_syn(p, pos), r);
      }
      *pos = *pos - 1;
      return (r);
    }
    default:
      return (str_to_node(t));
  }
}

p_sample.c


#include <stdio.h>
#include <stdlib.h>

#include "p_lex.h"
#include "p_syn.h"

void _p_print(node_t p)
{
  if (p == NULL) {
    printf("]");
  } else if (n_str(p)) {
    printf("'%s'", node_to_str(p));
  } else {
    if (n_btr(bt_x(p))) printf("[");
    _p_print(bt_x(p));
    if (bt_y(p) != NULL) printf(", ");
    _p_print(bt_y(p));
  }
}
void p_print(node_t p)
{
  if (n_btr(p)) { printf("["); _p_print(p); }
  else printf("'%s'", node_to_str(p));
}

int main(void)
{
  char p[SSTR_MAX], c = getchar();
  int i;
  for (i = 0; c != '\n'; i++, c = getchar()) p[i] = c;
  p[i] = '\0';

  char *pl[SSTR_MAX];
  int len = p_lex(p, pl) - 1;
  node_t r = p_syn(pl, &len);

  p_print(r); printf("\n");

  return (0);
}
$ ls
p_lex.c  p_lex.h  p_sample.c  p_syn.c  p_syn.h
$ cc -Wall -o p_sample *.c
$ ./p_sample
{"a": [100, f], "b": {"a": [t, "c"], "b": "d"}}
[['a'], ':', ['100', ',', 'f'], ',', ['b'], ':', [['a'], ':', ['t', ',', ['c']], ',', ['b'], ':', ['d']]]

Exemple d'implémentation Ruby

Presque le même que la version Python.

p_lex.rb


def p_lex(p)
  for s in ['(',')','[',']','{','}','"',','] do
    p = p.gsub(s, ' ' + s + ' ')
  end
  return p.split
end

p_syn.rb


def p_syn_rp(lp)
  case lp
    when '(' then ')'
    when '[' then ']'
    when '{' then '}'
    when '"' then '"'
  end
end

def p_syn(p)
  t = p.shift
  if ['(','[','{','"'].include?(t) then
    r = []
    while p[0] != p_syn_rp(t) do
      r += [p_syn(p)]
    end
    p.shift
    return r
  else
    return t
  end
end
>> p_syn(p_lex(gets.chomp))
{"a": [100, f], "b": {"a": [t, "c"], "b": "d"}}
=> [["a"], ":", ["100", ",", "f"], ",", ["b"], ":", [["a"], ":", ["t", ",", ["c"]], ",", ["b"], ":", ["d"]]]

Exemple d'implémentation JavaScript

Presque le même que la version Python.

p_lex.js


function p_lex(p) {
  p = p.replace(/(\(|\)|\[|\]|\{|\}|\"|\,)/g, ' $1 ');
  return p.split(/\s+/).filter(x => x != '');
}

p_syn.js


p_syn_rp = {'(':')','{':'}','[':']','"':'"'};
function p_syn(p) {
  var t = p.shift();
  if (['(','{','[','"'].includes(t)) {
    var r = [];
    while (p[0] != p_syn_rp[t]) {
      r = r.concat([p_syn(p)]);
    }
    p.shift();
    return r;
  } else {
    return t;
  }
}
> p_syn(p_lex('{"a": [100, f], "b": {"a": [t, "c"], "b": "d"}}'))
[ [ 'a' ],
  ':',
  [ '100', ',', 'f' ],
  ',',
  [ 'b' ],
  ':',
  [ [ 'a' ], ':', [ 't', ',', [Array] ], ',', [ 'b' ], ':', [ 'd' ] ] ]

Remarques

Informations complémentaires sur l'article

Journal des modifications

Recommended Posts

"Chaîne de caractères parentaux" Résumé de l'exemple d'implémentation d'un analyseur simple
Résumé de la chaîne de caractères 1
Exemple d'implémentation simple d'un type d'augmentation de données
Animation de chaîne simple
Plage de caractères / plage de chaînes de caractères
Exemple d'implémentation d'un système de traitement LISP simple (version Python)
Mémo de création de pilote de périphérique de caractère simple (implémentation lecture / écriture)