[HELP] Modélisation d'un parser HTML

Version imprimable

12/01/2004, 22h24
dazulu

[HELP] Modélisation d'un parser HTML

Bonjour à toutes et à tous,

à titre d'exercice, je dois actuellement modéliser un parser html. En fait, il s'agit pour moi d'écrire des règles inductives qui décrivent l'état de la page html que l'on cherche à afficher (donc, écriture de la sémantique d'évaluation). On m'a donné la syntaxe abstraite suivante :

Gatégories syntaxiques :

C == a | b | ....|z |A | ... | Z|0|1...| 9| ;|.|…

S == [] | C S

s in S
i in item

h in Html
b in Blocks

ref = reference on files or other web pages

b ==
bold( i ) | % bold <b> S </b>
italic( i ) | % italic <i> S </i>
head1( i ) | % head <h1> S </h1>
head2( i ) | % head <h2> S </h2>
...
head6( i ) | % head <h6> S </h6>
hr|
hr(n)|
par(i) |
font(name,i)|
br | % break
link(ref,i)|
img(ref,x,y)

Structure globale :

h = html(head ,i)

head = title(i)

i = item(s,il,s')
il = b i | b

item = S item | Block | []

Et le problème, c'est que je ne vois pas du tout comment commencer :-(( Je ne vous demande pas de me pondre une réponse toute faite de mon exo, mais je suis par contre preneur de tous les coups de pouce que vous seriez prêts à me donner !!!

Merci d'avance,

Jean
12/01/2004, 22h35
ludovic.fernandez
Pour analyser ta grammaire, tu dois commencer par créer un parseur syntaxique : il va prendre en entrée un texte et le comparer avec une grammaire générique.

Exemple : Ce fichier doit être parser linéairement et accepter de passer à l'étape suivante.
Code:

1 2 3 4 5 6 <html> <body> Coucou ! </body> </html>
Exemple : Ce fichier doit donner une exception car il manque la balise </h1>, bref tu dois gérer toutes les erreurs possibles.
Code:

1 2 3 4 5 6 7 <html> <body> <h1> Coucou ! </body> </html>
Ensuite il faut continuer par un lexeur et enfin l'interpréteur (nous verrons ensuite ...)
12/01/2004, 22h47
dazulu

Hello,

En fait, à partire de cette syntaxe abstraite, je dois écrire une sémantique opérationnelle(par un ensemble de règles définies par induction... ceci doit me servir de base pour ensuite écrire un parser html en prolog dans une deuxièmre phase, sans passer par des outils de type lexx ou yacc). Mais comme je ne suis pas un as de ces histoires de syntaxes, je ne vois pas bien comment écrire cela...

Merci bien pour tes remarques ;-)

Jean

J'écrirai :

Code:

1
2
3
4
5
HTML &#58;&#58;= O_HTML EXPR  F_HTML
EXPR &#58;&#58;= O_BALISE EXPR F_BALISE | VIDE
O_BALISE &#58;&#58;= O_BODY | O_DIV | ....
F_BALISE &#58;&#58;= F_BODY | F_DIV | ....

En passant au fait qu'une O_BALISE dépend d'une F_BALISE ceci reviendrait au fait :

Code:

1
2
3
4
HTML &#58;&#58;= O_HTML EXPR  F_HTML
EXPR &#58;&#58;= O_BODY SS_EXPR F_BODY | VIDE
SS_EXPR &#58;&#58;= O_DIV SS_EXPR F_DIV | O_HIDEN SS_EXPR F_HIDEN ...

12/01/2004, 23h04
dazulu

Merci beaucoup, quelle rapidité :D Donc, si j'ai bien compris ce que tu as marqué, on commence par définir tous les types de balises (définis dans la syntaxque abstraite) que le parseur peut être ammené à traiter et ensuite on modélise l'ensemble des états par lequel passe mon parseur après chaque lecture d'une balise ? Est-ce correct ?

Là c'est moi qui ne te comprends pas :oops: . En fait je t'ai écris le début de la grammaire d'un façon allégée puisqu'il manque quelques traits concrets du langage. Cependant, j'essaie de traiter par une grammaire toutes les possiblités.

J'entre dans mon parseur la ligne suivante : (d'ailleurs une EXPR peut être une SS_EXPR et une SS_EXPR peut être un texte) <HTML><BODY><H1>toto</H1></BODY></HTML> cette ligne va être comparée à ma grammaire générique, si elle n'y répond pas c'est une exception ! (dans ce cas elle doit fonctionner)
Code:

1 2 3 4 1°étape : <HTML> est comparée à O_HTML, <BODY><H1>toto</H1></BODY> est comparé à EXPR et </HTML> à F_HTML => Pas d'exception 2°étape : <BODY> est comparé à O_BODY, <H1>toto</H1> à SS_EXPR et </BODY> à F_BODY => Pas d'exception 3°étape : <H1> est comparé à O_H1, toto à SS_EXPR et F_H1 à </H1> ...etc
Remarque : Lors de la définition d'une grammaire, celle ci ne doit pas être récursive à GAUCHE !

13/01/2004, 12h17
dazulu

Salut,

en fait, je crois que j'ai été un peu vite en besogne en parlant de la syntaxe concrète... En fait, je dois surtout modéliser les étapes de traitement à l'aide de règles inductives (sémantique opérationnelle).

Par exemple, nous avons dû modéliser le comprtement d'une machine à calculer. Pour cela, on a dû définir un certain nombre d'éléments (écran, touche etc...) Puis l'état de de l'écran et de la pile de la machine après chaque appui sur une touche, à partir de règles inductives (par exemple l'état de l'affichage et de la pile après appui sur la touche enregistre:

<écran, pile> ---"record"---> <vide, pile::écran> ).

Je dois faire un peu la même chose avec le html, mais ne comprends pas par quel bout commencer :-((

Merci infiniment,

J
13/01/2004, 20h20
ludovic.fernandez
Je ne suis pas certain de te comprendre : je n'ai jamais fait un tel exercice. Mais j'imagine que tu dois expliquer alors le traitement du HTML. on utilise une pile :
Code:

1 2 3 <O_BALISE> --> Ajoute balise pile </F_BALISE> --> Retire balise pile
Ce qui donne :
Code:

1 2 3 <O_BALISE, STACK> ----> <NEXT, STACK+=O_BALISE> ...... ..... <F_BALISE, STACK> ---> <NEXT, STACK-=O_BALISE>
Je ne pourrais t'en dire plus, c'est le fonctionnement d'un registre à pile.
13/01/2004, 20h41
dazulu

En fait, l'histoire de la pile était un exemple :wink: Mais ce que tu as écrit me donne une ou deux idées quand même... Mais j'ai encore du pain sur la planche ;-)

Merci beaucoup,

Jean
31/07/2006, 00h39
pirus

salut,

ca tombe bien que vous parliez de ca il-y-a 2 ans 1/2, car nous avons justement un petit thread en cours a ce sujet :)

il s'agit de realiser un parser sachant extraire les liens d'un flux HTML. oui, je sais, ca semble idiot, mais le probleme est manifestement toujours d'actualite, et vous pouvez devenir celebres car un concours a ete lance a cette occasion ! 8-) (et qui sait.. peut-etre pourra-t-on en faire quelque-chose de serieux ensuite)

plus d'infos sont disponibles ici.

alors a vos claviers ! c'est l'occasion de prouver une fois de plus a la planete entiere que les developpeurs de devnet ne sont pas des tafioles :)

-pirus.
31/07/2006, 00h48
Luc Hermitte

Code:

il s'agit de réaliser un parser sachant extraire les liens d'un flux HTML.

man egrep.
Parfois il y a des outils qui marchent très bien, et il est inutile de sortir l'artillerie.
31/07/2006, 01h03
pirus

Citation:

Envoyé par Luc Hermitte

man egrep.
Parfois il y a des outils qui marchent très bien, et il est inutile de sortir l'artillerie.

s'il te plait, ne me la fais pas :)

on sait tres bien que ca peut etre beaucoup plus complique que ca, pour des tas de raisons. meme si l'objet de mon message peut sembler stupide a premiere vue, l'interet du concours en question est justement didactique, et a mon avis pas incompatible avec la vocation de developpez.net.

nous sommes justement a la recherche d'un admin pouvant nous aider a communiquer la-dessus, car a ma connaissance il n'existe pas d'endroit sur le site pour porter ce genre d'initiatives.

chaque contribution est la bienvenue..

merci,
-pirus.