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.
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.
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.
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']]]
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']]]
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"]]]
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' ] ] ]
s_syn pour une raison quelconque ... "[Algorithme de la voie ferrée](https://ja.wikipedia.org/wiki/%E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0) »est différent.Recommended Posts