it

 

Your company develops a variety of web-based products. Many tools for transforming HTML (the language of web pages) require those pages to be written in a ?disciplined? dialect of HTML called XHTML. One of the key factors distinguishing XHTML from ordinary HTML is that all opening and closing tags in XHTML must be properly balanced.

You have been asked to write a validator that can examine an XHTML file for this balancing.

HTML is a ?mark-up? language in which ordinary text is interspersed with ?tags? that introduce formatting properties. Tags are written inside < > brackets. There are three forms of tags:

• opening tags: ?<whatever?>? The ... may be empty or may contain one or more attributes, separated from the tag name by at least one whitespace character. Attributes will be ignored in this assignment.
• closing tags: ?</whatever?>? The ... may be empty or whitespace characters.
• singleton tags: ?<whatever?/>? The ... may be empty or may contain one or more attributes, separated from the tag name by at least one whitespace character.

For example, here is a snippet of HTML in which I have highlighted the opening tags, closing tags, and singleton tags:

<p>

For example, here is a snippet of HTML in which

I have highlighted the <span class="high1">opening

tags</span>, <span class="high2">closing

tags</span>, and

<span class="high3">singleton tags</span>:

</p>

<hr/>

Most tags occur in pairs, in which an opening tag <whatever...> is closed by a similar tag with a / at the start of its name: </whatever>. For example, web pages can get bold text this way: <b>bold</b> and italic text this this way: <i>italic</i>. Notice that the tag names are case sensitive in XHTML. Pairs of tags may be nested: <i>like <b>this</b></i> to produce text _like this _, but may not overlap <b>like <big>this</b></big>. Consequently, a tag with a / must always match the most recently seen non-/ paired tag. That rule suggests the use of stacks.

Some tags are singletons, not occurring in pairs. These are signaled by a ?/? just before the closing >. For example, <hr/> produces a horizontal rule:

1. Files for this assignment may be found here or, if you are logged in to one of the CS Dept. Linux machines, in ~zeil/Assignments/cs361/stack_xhtml/.
2. You are given a driver for the XHTML validator. The code you are provided with will read an XHTML file and scan for any tags. It passes each tag it encounters to a Balancer whose job is to make sure that the tags are occurring in properly balanced pairs.
   The driver is designed to take the path to the file to be checked as a command line parameter.
   ./xmlcheck test0.html 
3. You must supply the Balancer class. This class must use a std::stack as its primary data member. (You may have additional simple data members, bools or ints, but no containers other than the stack.) The two most critical operations the Balancer class must support are
   • tag(string atag): indicates that the driver has encountered a tag. The full text of the tag is passed as the parameter atag. This may be an opening tag, a closing tag, or a singleton tag.
   • status(): returns a single int indicating the status of what has been observed so far:
     • -1 indicates that an error has been detected.
     • 0 indicates that no error has been detected, but that one or more opening tags have yet to be matched
     • 1 indicates that no error has been detected and there are no opening tags that have yet to be matched against a closing tag.
4. As in the prior assignments, you also will be provided with unit tests for the class that you are working on (Balancer);
   There is also a pair of test files test0.dat and test1.dat that you can use to test the full xmlcheck program. test0.html should be reported as OK, but test1.html has mismatched tags. As always, you should conduct additional systems testing with your own test cases.

FlexLexer.h

// -*-C*-
// FlexLexer.h — define interfaces for lexical analyzer classes generated
// by flex

// Copyright (c) 1993 The Regents of the University of California.
// All rights reserved.
//
// This code is derived from software contributed to Berkeley by
// Kent Williams and Tom Epperly.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:

// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.

// Neither the name of the University nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.

// THIS SOFTWARE IS PROVIDED “AS IS” AND WITHOUT ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE.

// This file defines FlexLexer, an abstract class which specifies the
// external interface provided to flex C lexer objects, and yyFlexLexer,
// which defines a particular lexer class.
//
// If you want to create multiple lexer classes, you use the -P flag
// to rename each yyFlexLexer to some other xxFlexLexer. You then
// include <FlexLexer.h> in your other sources once per lexer class:
//
// #undef yyFlexLexer
// #define yyFlexLexer xxFlexLexer
// #include <FlexLexer.h>
//
// #undef yyFlexLexer
// #define yyFlexLexer zzFlexLexer
// #include <FlexLexer.h>
// …

#ifndef __FLEX_LEXER_H
// Never included before – need to define base class.
#define __FLEX_LEXER_H

#include <iostream>

extern “C” {

struct yy_buffer_state;
typedef int yy_state_type;

class FlexLexer
{
public:
virtual ~FlexLexer() { }

const char* YYText() const { return yytext; }
int YYLeng() const { return yyleng; }

virtual void
yy_switch_to_buffer( yy_buffer_state* new_buffer ) = 0;
virtual yy_buffer_state* yy_create_buffer( std::istream* s, int size ) = 0;
virtual yy_buffer_state* yy_create_buffer( std::istream& s, int size ) = 0;
virtual void yy_delete_buffer( yy_buffer_state* b ) = 0;
virtual void yyrestart( std::istream* s ) = 0;
virtual void yyrestart( std::istream& s ) = 0;

virtual int yylex() = 0;

// Call yylex with new input/output sources.
int yylex( std::istream& new_in, std::ostream& new_out )
{
switch_streams( new_in, new_out );
return yylex();
}

int yylex( std::istream* new_in, std::ostream* new_out = 0)
{
switch_streams( new_in, new_out );
return yylex();
}

// Switch to new input/output streams. A nil stream pointer
// indicates “keep the current one”.
virtual void switch_streams( std::istream* new_in,
std::ostream* new_out ) = 0;
virtual void switch_streams( std::istream& new_in,
std::ostream& new_out ) = 0;

int lineno() const { return yylineno; }

int debug() const { return yy_flex_debug; }
void set_debug( int flag ) { yy_flex_debug = flag; }

protected:
char* yytext;
int yyleng;
int yylineno; // only maintained if you use %option yylineno
int yy_flex_debug; // only has effect with -d or “%option debug”
};

}
#endif // FLEXLEXER_H

#if defined(yyFlexLexer) || ! defined(yyFlexLexerOnce)
// Either this is the first time through (yyFlexLexerOnce not defined),
// or this is a repeated include to define a different flavor of
// yyFlexLexer, as discussed in the flex manual.
# define yyFlexLexerOnce

extern “C” {

class yyFlexLexer : public FlexLexer {
public:
// arg_yyin and arg_yyout default to the cin and cout, but we
// only make that assignment when initializing in yylex().
yyFlexLexer( std::istream& arg_yyin, std::ostream& arg_yyout );
yyFlexLexer( std::istream* arg_yyin = 0, std::ostream* arg_yyout = 0 );
private:
void ctor_common();

public:

virtual ~yyFlexLexer();

void yy_switch_to_buffer( yy_buffer_state* new_buffer );
yy_buffer_state* yy_create_buffer( std::istream* s, int size );
yy_buffer_state* yy_create_buffer( std::istream& s, int size );
void yy_delete_buffer( yy_buffer_state* b );
void yyrestart( std::istream* s );
void yyrestart( std::istream& s );

void yypush_buffer_state( yy_buffer_state* new_buffer );
void yypop_buffer_state();

virtual int yylex();
virtual void switch_streams( std::istream& new_in, std::ostream& new_out );
virtual void switch_streams( std::istream* new_in = 0, std::ostream* new_out = 0 );
virtual int yywrap();

protected:
virtual int LexerInput( char* buf, int max_size );
virtual void LexerOutput( const char* buf, int size );
virtual void LexerError( const char* msg );

void yyunput( int c, char* buf_ptr );
int yyinput();

void yy_load_buffer_state();
void yy_init_buffer( yy_buffer_state* b, std::istream& s );
void yy_flush_buffer( yy_buffer_state* b );

int yy_start_stack_ptr;
int yy_start_stack_depth;
int* yy_start_stack;

void yy_push_state( int new_state );
void yy_pop_state();
int yy_top_state();

yy_state_type yy_get_previous_state();
yy_state_type yy_try_NUL_trans( yy_state_type current_state );
int yy_get_next_buffer();

std::istream yyin; // input source for default LexerInput
std::ostream yyout; // output sink for default LexerOutput

// yy_hold_char holds the character lost when yytext is formed.
char yy_hold_char;

// Number of characters read into yy_ch_buf.
int yy_n_chars;

// Points to current character in buffer.
char* yy_c_buf_p;

int yy_init; // whether we need to initialize
int yy_start; // start state number

// Flag which is used to allow yywrap()’s to do buffer switches
// instead of setting up a fresh yyin. A bit of a hack …
int yy_did_buffer_switch_on_eof;

size_t yy_buffer_stack_top; /**< index of top of stack. */
size_t yy_buffer_stack_max; /**< capacity of stack. */
yy_buffer_state ** yy_buffer_stack; /**< Stack as an array. */
void yyensure_buffer_stack(void);

// The following are not always needed, but may be depending
// on use of certain flex features (like REJECT or yymore()).

yy_state_type yy_last_accepting_state;
char* yy_last_accepting_cpos;

yy_state_type* yy_state_buf;
yy_state_type* yy_state_ptr;

char* yy_full_match;
int* yy_full_state;
int yy_full_lp;

int yy_lp;
int yy_looking_for_trail_begin;

int yy_more_flag;
int yy_more_len;
int yy_more_offset;
int yy_prev_more_offset;
};

}

#endif // yyFlexLexer || ! yyFlexLexerOnce