Was für ein Parser ist, dass er die Verarbeitung wie im folgenden Python-Ausführungsbeispiel ausführt.
>>> p_syn(p_lex(input()))
((10 + 20)*(30 - 40))
[['10', '+', '20'], '*', ['30', '-', '40']]
>>> p_syn(p_lex(input()))
{ "color": [ "red", "green" ] }
[['color'], ':', [['red'], ',', ['green']]]
Ich bin dabei, einen einfachen Parser vom Typ S in verschiedenen Programmiersprachen mit verschiedenen Gründen zu erstellen, aber mit einer geringfügigen Änderung einen einfachen JSON-Parser Ist es nicht auch? Als ich das bemerkte, entschied ich mich, ein Beschreibungsbeispiel zusammenzustellen, das sowohl für den JSON-Parser als auch für den Parser vom Typ S oder den Parser für die ursprüngliche Datenstrukturdarstellung in Klammern mit ein wenig Änderung und zusätzlicher Verarbeitung einfach implementiert werden kann. [Phrasenanalyse] beschränkt auf Klammern (https://ja.wikipedia.org/wiki/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90) + Abstract Syntaxbaum Generierung Daher kann es möglich sein, nur den Teil der Phrasenanalyse oder nur den Teil der Erzeugung des abstrakten Syntaxbaums umzuleiten.
p_lex Funktion (Phrasenanalyse Teil)Aus der eingegebenen Zeichenfolge wird ein Zeichenfolgenarray mit () [] {}", als Phrase und blank als Trennzeichen generiert.
[Beispiel] {(10 + 20) * (30 -40)}
⇒['{', '(', '10', '+', '20', ')', '*', '(', '30', '-', '40', ')', '}']
Wenn Sie es als Beispiel für ein sogenanntes Taschenrechnerprogramm verwenden möchten, möchten Sie möglicherweise zusätzlich Operatoren wie + -`` * / als Phrasen erkennen.
p_syn Funktion (abstrakter Syntaxbaumgenerator)Generieren Sie eine Liste von () [] {}" Gruppen aus dem obigen Zeichenfolgenarray.
[Beispiel] ['{', '(', '10', '+', '20', ')', '*', '(', '30', '-', '40', ' ) ','} ']
⇒[['10', '+', '20'], '*', ['30', '-', '40']]
, : . usw. bleiben als Listenelemente erhalten, sodass je nach Zweck der Umleitung, gelöscht wird und A: B und A. B eine Liste von Schlüsseln und Werten sind. , Etc. kann erforderlich sein. Wenn Sie die Verarbeitung abhängig von der Art der Klammer ändern möchten, müssen Sie einige Anpassungen vornehmen.
Ein beträchtlicher Teil wird von "tokenize" und "read_from_tokens" von Peter Norvigs "lis.py" abgelenkt. Um den Vergleich mit Implementierungsbeispielen in anderen Sprachen zu erleichtern, wurde die Beschreibung ohne Verwendung von "pop" und "append" geändert.
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']]]
Erstellt mit der Python-Version als Modell. Der Abschnitt zur Phrasenanalyse verwendet "strtok". Im abstrakten Syntaxbaumgenerierungsteil wird eine Listenstruktur durch einen dichotomisierten Baum gemäß unserem Hobby (?) Erzeugt. Aus diesem Grund scannt p_syn das Zeichenfolgenarray von hinten.
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']]]
Fast das gleiche wie die Python-Version.
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"]]]
Fast das gleiche wie die Python-Version.
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 bezieht ... "[Trainway-Algorithmus](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) “ist anders.Recommended Posts