[HELP] Modélisation d'un parser HTML

**dazulu** · 12/01/2004, 22h24

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

**ludovic.fernandez** · 12/01/2004, 22h35

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ...)

**dazulu** · 12/01/2004, 22h47

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

**ludovic.fernandez** · 12/01/2004, 22h54

J'écrirai :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ...

**dazulu** · 12/01/2004, 23h04

Merci beaucoup, quelle rapidité

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 ?

**ludovic.fernandez** · 12/01/2004, 23h13

Là c'est moi qui ne te comprends pas

. 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
1°étape &#58; <HTML> est comparée à O_HTML, <BODY><H1>toto</H1></BODY> est comparé à EXPR et </HTML> à F_HTML => Pas d'exception
2°étape &#58; <BODY> est comparé à O_BODY, <H1>toto</H1> à SS_EXPR et </BODY> à F_BODY => Pas d'exception
3°étape &#58; <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 !

**dazulu** · 13/01/2004, 12h17

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

**ludovic.fernandez** · 13/01/2004, 20h20

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
<O_BALISE>  --> Ajoute balise pile
</F_BALISE>  --> Retire balise pile

Ce qui donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**dazulu** · 13/01/2004, 20h41

En fait, l'histoire de la pile était un exemple

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

**pirus** · 31/07/2006, 00h39

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 !

(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.

**Luc Hermitte** · 31/07/2006, 00h48

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**pirus** · 31/07/2006, 01h03

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.

[HELP] Modélisation d'un parser HTML

Langages de programmation

Discussions similaires

Partager

Partager