Compiler Ch5 LL Parser

First L: 由左到右處理input

Second L: 執行left derivation

LL(K): K代表向前探查K個token

LL(1)

由左到右處理字串，再對句型執行最左推導語法樹，只需向前查看(偷偷看)1個token，就可以推導出來的文法，即是LL(1)，當 parser 遇到多種可能的推導方式時，偷偷的看 Predict Set ，找出對應Token ，持續parse直到$

如何計算 Predict Set (所有可能的下一個token)

如果 A -> ABCD

ANS = First(ABCD) #找出第一個terminal


if (ABCD -> λ):     #如果會derive 出 lumbda
    ANS = ANS 聯集 Follow(A)     #那就要再從follow找terminal
    
return(ANS)     #回傳答案

如何確認 Grammer 是 LL(1)

如果 S -> A | B

要符合 LL(1) 的 grammer 有以下條件

1. First(A) 跟 First(B) 交集為空
2. 兩者至多一個可 derive lumbda
3. if B -> lumbda , First(A) 跟 Follow(S) 交集為空
4. if A -> lumbda , First(B) 跟 Follow(S) 交集為空

Example

Rule：

S -> A C $
C -> c | λ
A -> a B C d | B Q
B -> b B | λ
Q -> q | λ

建表

檢查條件

檢查4種條件，若都符合即是LL(1)

Recursive-Descient Parser with LL(1)

這種parser搭配LL(1)，大致結構就是LL方式判斷，依照rule去match terminal，若是nonterminal，則call它的rule繼續match，遞迴下去求得解答或是判斷出syntax error

Database Ch3 ER Model

E:entity
R:relationship

ER model 是 database 設計的一種流程

範例:

ER model 常用符號:

Entity: 用來詮釋Mini World的一些物件，大部分是名詞，例如在公司中，有員工 部門 專案 這些entity

Relationship: 用來表示Entity間的關係，就像是離散數學中的relation概念差不多。

Attribute: Entity 或 relationship 的 屬性，例如員工這個Entity有名子 性別 等等屬性

Entity type & key attribute

Entity type:有相同基本類型的entity，可分類成entity type 例如員工type ， Project type

Key attribute:在Entity type中，每個entity的這個attribute都不同，則為key attribute，像是身分證號碼

Relationship & Relation type

一樣同樣type 的 relation 會分到一個relation type

參與這個relation的entity數 = degree

Relationship 可以relate相同的entity type中的entity
例如 上司關係(員工A,員工B) 員工A是員工B的上司，兩個員工都是屬於員工type

Structural Constraints and Roles

Cardinality Ratio:代表不同個體之間在參與某一個關係時，個體間的實例相互參與之數量比

常見有 1:1 1:N M:N

Participation Constraint:是指某個體中的所有實例，是否一定需要依靠參與某關係，並和另一個體產生關聯而存在。

全部參與 (Total Participation)
部份參與 (Partial Participation)

Min Max Notation:

用來定義relation的參與entity數的最小與最大值
Default: Min=0,Max=1

Weak Entity

弱實體就是必須依靠其他實體才能存在。如果弱實體所依靠的實體消失了, 則該弱實體也就變得沒有意義了。

參考資料

1. 李強老師ppt
2. http://sjchen.im.nuu.edu.tw/Database/99/Ch03.pdf
3. http://spaces.isu.edu.tw/upload/19225/0/news/postfile_308.pdf
4. http://www.mysql.tw/2013/03/entity-relationship-model.html

Database Ch2 DBMS概念與架構

Data Model

Data Model: 一組用來描述資料庫結構的概念

Data Model Operation: 依據資料模型指定存取及更新資料庫的動作。在資料模型上的運算可能包含「基本運算」和「使用者定義的運算」

Data Model 的分類：

1. Conceptional(high-level):容易讓使用者理解
2. Physical(low level):表現資料實際在電腦的儲存方式
3. Implementation(record-oriented):介於以上兩者之間

Schema

Database Schema: 資料庫的綱要，包括資料庫的描述與一些限制
Database Instance: 資料庫實例，在某個特殊時間點的資料庫狀態(內容)

Three schema architecture

Internal schema: 描述實際的資料庫儲存結構。通常是使用實體（physical model）資料模型

Conceptional schema: 是用來為某一組使用者描述整個資料庫的結構與限制。通常是使用某種概念 (conceptual) 或實作
（implementation）資料模型

External schema: 是用來描述各個不同的使用者檢視表 (view)。它通常使用與概念層相同的資料模型

Data Independence

Logical Data Independence: 代表修改Conceptional 時，不必修改 External

Physical Data Independence: 代表修改 Internal時，不必修改 Conceptional

DBMS Language

Data Defination Language(DDL): 是一種能讓DBA與資料庫設計師用來定義Conceptional schema，某些DDL也會定義 Internal （用storage definition language，SDL）與 External （用view definition language，VDL）

Data Maniputation Language(DML): 用來指定資料庫的擷取與修改

DML Command(Data sublangage):

可以嵌入在一般的程式語言裡（主機語言，host
language），如COBOL、C或組合語言，或者是直接執行獨立的（stand-alone）DML命令（也就是查詢語言，query language）

Type of DML

Procedural DML：低階或程序化的，一次一筆記錄；它們是指定如何擷取資料，並且具有如迴圈這類的程式結構

Non-procedural DML：高階或非程序化的，它們是集合導向的（set-oriented），而且是指定要什麼資料，而不是如何擷取，如SQL。也稱作宣告式（declarative）語言

DBMS 分類

依照Data Model分類:
傳統的：Relational, Network, Hierarchical
新興的：Object-oriented, Semantic, Entity-Relationship, other

Database Ch1

基本概念

1. Database：Data的集合(Collaction)
2. Mini-world：微小世界，用來詮釋真實世界一部分
3. DBS：資料庫系統
4. DBMS：資料庫管理系統
5. DB：資料庫

DBMS的目錄(catalog) 中儲存有資料庫的描述，這些描述資料稱為詮釋資料 (metadata)。因此DBMS軟體能與不同的資料庫一起工作

資料庫的使用者

Worker on the scene(檯面上的人):

1. Database adminstrators(DBAs): 負責授權存取資料庫、協調及監督資料庫的使用、取得軟硬體資源、控制它的使用和監督運作的效能
2. Database Designer: 負責定義資料庫的內容、結構、限制，以及函數和交易。他們必須與終端使用者溝通以了解他們的需求
3. 終端使用者：他們會查詢和使用資料來製作報表，其中一部分人可以修改資料庫的內容

Worker behinh the scene:

1. DBMS designers and implementers: 負責資料庫管理系統的開發
2. Tool developer: 開發DBMS的tools
3. Operators and maintenance personel:管理database的硬體環境與軟體環境

參考資料

1. 李強老師ppt
2. 台大kkchen ppt http://www.lis.ntu.edu.tw/~khchen/course/db/db2007/DBCh01Intro.pdf

Web Crawler In Perl 網路爬蟲

Readme

Sample code Using Regular Expression

use LWP::Simple;
use LWP::UserAgent;
use HTTP::Request;
use HTTP::Response;
use HTML::LinkExtor;
use Encode;
$browser = LWP::UserAgent->new();
$browser->timeout(10);
&crawler('http://www.atmovies.com.tw/showtime/t06607/a06/');
&crawler('http://www.atmovies.com.tw/showtime/t06608/a06/');
&crawler('http://www.atmovies.com.tw/showtime/t06609/a06/');
sub crawler{
 (my $URL) =@_;
 my $request = HTTP::Request->new(GET => $URL);
 my $response = $browser->request($request);
 if ($response->is_error()) {printf "%s\n", $response->status_line;}

 $contents =   $response->content();
 $data =  $contents;
 while($data =~ m!<ul id="theaterShowtimeTable">(.*?)<ul>(.*?)</ul>(.*?)</ul>!gs)
 {
  $item=$1;
  $otherparse=$3;
  $item =~ m!<a href=(.*)>(.*?)</a>!;
  $title=$2;
  print "$title\n";
  while($otherparse =~m!(\d)(\d)：(\d)(\d)!gs)
  {
   print "$1$2:$3$4\n";
  }
 }
}

sample code using TreeBuilder

use HTML::TreeBuilder;
binmode(STDIN, ':encoding(utf8)');
binmode(STDOUT, ':encoding(utf8)');
binmode(STDERR, ':encoding(utf8)');


$URL = 'http://www.atmovies.com.tw/showtime/t06607/a06/';

my $tree = HTML::TreeBuilder->new_from_url($URL);
my @items = $tree->look_down('id', 'theaterShowtimeTable' )or die("no items: $!\n");
for my $item (@items) 
{
    my @movies = $item->look_down( '_tag', 'li' )
    or die("no movies$!\n");
    $count=0;
    for my $movie (@movies)
    {
        if($count!=1&&$count!=2&&$count!=3)
     {
            if($movie->attr('class') ne "theaterElse" && $movie->attr('class') ne "filmVersion")
         { 
          print $movie->as_text, "\n";
      }
     }
        $count++;
     }
        
        
}

Compiler Ch4-Grammer

First and follow

是兩個很重要的Function，用來建構top-down 跟 bottom-up Parser

假設rule是以下這些
S -> ABc
A -> a | B
B -> b | λ

1.First(T)

定義：

將 T (可以是terminal 或 nonterminal) 展開時，可能遇到的第一個 terminal symbol 所成的集合
所以

First(A) = { a , b , λ }

First(B) = { b , λ }

2.Follow(T)

定義：

接在T( nonterminal ) 後所有可能的第一個terminal
在開始算Follow之前，先把$(input right end marker)放到Start symbol後
所以

Follow(B) = { c , $}

Follow(A) = First(B) + Follow(B) = { b , c }

在算Follow(A)時，即是在找接在A之後的第一個terminal有哪些，
而 S->ABc 因此去尋找B的First set，即是在找A後的第一個terminal，
會發現 First(B) 有 λ，因此當B->λ時，A後的第一個Terminal在Follow(B)內，以此類推。