lexer.go 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765
  1. /*
  2. * Public Domain Software
  3. *
  4. * I (Matthias Ladkau) am the author of the source code in this file.
  5. * I have placed the source code in this file in the public domain.
  6. *
  7. * For further information see: http://creativecommons.org/publicdomain/zero/1.0/
  8. */
  9. package parser
  10. import (
  11. "bytes"
  12. "encoding/json"
  13. "fmt"
  14. "regexp"
  15. "strconv"
  16. "strings"
  17. "unicode"
  18. "unicode/utf8"
  19. )
  20. var namePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  21. var numberPattern = regexp.MustCompile("^[0-9].*$")
  22. /*
  23. LexToken represents a token which is returned by the lexer.
  24. */
  25. type LexToken struct {
  26. ID LexTokenID // Token kind
  27. Pos int // Starting position (in bytes)
  28. Val string // Token value
  29. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  30. Lline int // Line in the input this token appears
  31. Lpos int // Position in the input line this token appears
  32. }
  33. /*
  34. NewLexTokenInstance creates a new LexToken object instance from given LexToken values.
  35. */
  36. func NewLexTokenInstance(t LexToken) *LexToken {
  37. return &LexToken{
  38. t.ID,
  39. t.Pos,
  40. t.Val,
  41. t.Identifier,
  42. t.Lline,
  43. t.Lpos,
  44. }
  45. }
  46. /*
  47. Equal checks if this LexToken equals another LexToken. Returns also a message describing
  48. what is the found difference.
  49. */
  50. func (n LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  51. var res = true
  52. var msg = ""
  53. if n.ID != other.ID {
  54. res = false
  55. msg += fmt.Sprintf("ID is different %v vs %v\n", n.ID, other.ID)
  56. }
  57. if !ignorePosition && n.Pos != other.Pos {
  58. res = false
  59. msg += fmt.Sprintf("Pos is different %v vs %v\n", n.Pos, other.Pos)
  60. }
  61. if n.Val != other.Val {
  62. res = false
  63. msg += fmt.Sprintf("Val is different %v vs %v\n", n.Val, other.Val)
  64. }
  65. if n.Identifier != other.Identifier {
  66. res = false
  67. msg += fmt.Sprintf("Identifier is different %v vs %v\n", n.Identifier, other.Identifier)
  68. }
  69. if !ignorePosition && n.Lline != other.Lline {
  70. res = false
  71. msg += fmt.Sprintf("Lline is different %v vs %v\n", n.Lline, other.Lline)
  72. }
  73. if !ignorePosition && n.Lpos != other.Lpos {
  74. res = false
  75. msg += fmt.Sprintf("Lpos is different %v vs %v\n", n.Lpos, other.Lpos)
  76. }
  77. if msg != "" {
  78. var buf bytes.Buffer
  79. out, _ := json.MarshalIndent(n, "", " ")
  80. buf.WriteString(string(out))
  81. buf.WriteString("\nvs\n")
  82. out, _ = json.MarshalIndent(other, "", " ")
  83. buf.WriteString(string(out))
  84. msg = fmt.Sprintf("%v%v", msg, buf.String())
  85. }
  86. return res, msg
  87. }
  88. /*
  89. PosString returns the position of this token in the origianl input as a string.
  90. */
  91. func (t LexToken) PosString() string {
  92. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  93. }
  94. /*
  95. String returns a string representation of a token.
  96. */
  97. func (t LexToken) String() string {
  98. prefix := ""
  99. if !t.Identifier {
  100. prefix = "v:" // Value is not an identifier
  101. }
  102. switch {
  103. case t.ID == TokenEOF:
  104. return "EOF"
  105. case t.ID == TokenError:
  106. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  107. case t.ID == TokenPRECOMMENT:
  108. return fmt.Sprintf("/* %s */", t.Val)
  109. case t.ID == TokenPOSTCOMMENT:
  110. return fmt.Sprintf("# %s", t.Val)
  111. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  112. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  113. case t.ID > TOKENodeKEYWORDS:
  114. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  115. case len(t.Val) > 20:
  116. // Special case for very long values
  117. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  118. }
  119. return fmt.Sprintf("%s%q", prefix, t.Val)
  120. }
  121. // Meta data interface
  122. /*
  123. Type returns the meta data type.
  124. */
  125. func (t LexToken) Type() string {
  126. if t.ID == TokenPRECOMMENT {
  127. return MetaDataPreComment
  128. } else if t.ID == TokenPOSTCOMMENT {
  129. return MetaDataPostComment
  130. }
  131. return MetaDataGeneral
  132. }
  133. /*
  134. Value returns the meta data value.
  135. */
  136. func (t LexToken) Value() string {
  137. return t.Val
  138. }
  139. /*
  140. KeywordMap is a map of keywords - these require spaces between them
  141. */
  142. var KeywordMap = map[string]LexTokenID{
  143. // Import statement
  144. "import": TokenIMPORT,
  145. "as": TokenAS,
  146. // Sink definition
  147. "sink": TokenSINK,
  148. "kindmatch": TokenKINDMATCH,
  149. "scopematch": TokenSCOPEMATCH,
  150. "statematch": TokenSTATEMATCH,
  151. "priority": TokenPRIORITY,
  152. "suppresses": TokenSUPPRESSES,
  153. // Function definition
  154. "func": TokenFUNC,
  155. "return": TokenRETURN,
  156. // Boolean operators
  157. "and": TokenAND,
  158. "or": TokenOR,
  159. "not": TokenNOT,
  160. // String operators
  161. "like": TokenLIKE,
  162. "hasprefix": TokenHASPREFIX,
  163. "hassuffix": TokenHASSUFFIX,
  164. // List operators
  165. "in": TokenIN,
  166. "notin": TokenNOTIN,
  167. // Constant terminals
  168. "false": TokenFALSE,
  169. "true": TokenTRUE,
  170. "null": TokenNULL,
  171. // Conditional statements
  172. "if": TokenIF,
  173. "elif": TokenELIF,
  174. "else": TokenELSE,
  175. // Loop statements
  176. "for": TokenFOR,
  177. "break": TokenBREAK,
  178. "continue": TokenCONTINUE,
  179. }
  180. /*
  181. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  182. Symbols can be maximal 2 characters long.
  183. */
  184. var SymbolMap = map[string]LexTokenID{
  185. // Condition operators
  186. ">=": TokenGEQ,
  187. "<=": TokenLEQ,
  188. "!=": TokenNEQ,
  189. "==": TokenEQ,
  190. ">": TokenGT,
  191. "<": TokenLT,
  192. // Grouping symbols
  193. "(": TokenLPAREN,
  194. ")": TokenRPAREN,
  195. "[": TokenLBRACK,
  196. "]": TokenRBRACK,
  197. "{": TokenLBRACE,
  198. "}": TokenRBRACE,
  199. // Separators
  200. ".": TokenDOT,
  201. ",": TokenCOMMA,
  202. ";": TokenSEMICOLON,
  203. // Grouping
  204. ":": TokenCOLON,
  205. "=": TokenEQUAL,
  206. // Arithmetic operators
  207. "+": TokenPLUS,
  208. "-": TokenMINUS,
  209. "*": TokenTIMES,
  210. "/": TokenDIV,
  211. "//": TokenDIVINT,
  212. "%": TokenMODINT,
  213. // Assignment statement
  214. ":=": TokenASSIGN,
  215. }
  216. // Lexer
  217. // =====
  218. /*
  219. RuneEOF is a special rune which represents the end of the input
  220. */
  221. const RuneEOF = -1
  222. /*
  223. Function which represents the current state of the lexer and returns the next state
  224. */
  225. type lexFunc func(*lexer) lexFunc
  226. /*
  227. Lexer data structure
  228. */
  229. type lexer struct {
  230. name string // Name to identify the input
  231. input string // Input string of the lexer
  232. pos int // Current rune pointer
  233. line int // Current line pointer
  234. lastnl int // Last newline position
  235. width int // Width of last rune
  236. start int // Start position of the current red token
  237. tokens chan LexToken // Channel for lexer output
  238. }
  239. /*
  240. Lex lexes a given input. Returns a channel which contains tokens.
  241. */
  242. func Lex(name string, input string) chan LexToken {
  243. l := &lexer{name, input, 0, 0, 0, 0, 0, make(chan LexToken)}
  244. go l.run()
  245. return l.tokens
  246. }
  247. /*
  248. LexToList lexes a given input. Returns a list of tokens.
  249. */
  250. func LexToList(name string, input string) []LexToken {
  251. var tokens []LexToken
  252. for t := range Lex(name, input) {
  253. tokens = append(tokens, t)
  254. }
  255. return tokens
  256. }
  257. /*
  258. Main loop of the lexer.
  259. */
  260. func (l *lexer) run() {
  261. if skipWhiteSpace(l) {
  262. for state := lexToken; state != nil; {
  263. state = state(l)
  264. if !skipWhiteSpace(l) {
  265. break
  266. }
  267. }
  268. }
  269. close(l.tokens)
  270. }
  271. /*
  272. next returns the next rune in the input and advances the current rune pointer
  273. if peek is 0. If peek is >0 then the nth character is returned without advancing
  274. the rune pointer.
  275. */
  276. func (l *lexer) next(peek int) rune {
  277. // Check if we reached the end
  278. if int(l.pos) >= len(l.input) {
  279. return RuneEOF
  280. }
  281. // Decode the next rune
  282. pos := l.pos
  283. if peek > 0 {
  284. pos += peek - 1
  285. }
  286. r, w := utf8.DecodeRuneInString(l.input[pos:])
  287. if peek == 0 {
  288. l.width = w
  289. l.pos += l.width
  290. }
  291. return r
  292. }
  293. /*
  294. backup sets the pointer one rune back. Can only be called once per next call.
  295. */
  296. func (l *lexer) backup(width int) {
  297. if width == 0 {
  298. width = l.width
  299. }
  300. l.pos -= width
  301. }
  302. /*
  303. startNew starts a new token.
  304. */
  305. func (l *lexer) startNew() {
  306. l.start = l.pos
  307. }
  308. /*
  309. emitToken passes a token back to the client.
  310. */
  311. func (l *lexer) emitToken(t LexTokenID) {
  312. if t == TokenEOF {
  313. l.emitTokenAndValue(t, "", false)
  314. return
  315. }
  316. if l.tokens != nil {
  317. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false,
  318. l.line + 1, l.start - l.lastnl + 1}
  319. }
  320. }
  321. /*
  322. emitTokenAndValue passes a token with a given value back to the client.
  323. */
  324. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool) {
  325. if l.tokens != nil {
  326. l.tokens <- LexToken{t, l.start, val, identifier, l.line + 1, l.start - l.lastnl + 1}
  327. }
  328. }
  329. /*
  330. emitError passes an error token back to the client.
  331. */
  332. func (l *lexer) emitError(msg string) {
  333. if l.tokens != nil {
  334. l.tokens <- LexToken{TokenError, l.start, msg, false, l.line + 1, l.start - l.lastnl + 1}
  335. }
  336. }
  337. // Helper functions
  338. // ================
  339. /*
  340. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  341. reaches EOF while skipping whitespaces.
  342. */
  343. func skipWhiteSpace(l *lexer) bool {
  344. r := l.next(0)
  345. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  346. if r == '\n' {
  347. l.line++
  348. l.lastnl = l.pos
  349. }
  350. r = l.next(0)
  351. if r == RuneEOF {
  352. l.emitToken(TokenEOF)
  353. return false
  354. }
  355. }
  356. l.backup(0)
  357. return true
  358. }
  359. /*
  360. lexTextBlock lexes a block of text without whitespaces. Interprets
  361. optionally all one or two letter tokens.
  362. */
  363. func lexTextBlock(l *lexer, interpretToken bool) {
  364. r := l.next(0)
  365. if interpretToken {
  366. // Check if we start with a known symbol
  367. nr := l.next(1)
  368. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  369. l.next(0)
  370. return
  371. }
  372. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  373. return
  374. }
  375. }
  376. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  377. if interpretToken {
  378. // Check if we find a token in the block
  379. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  380. l.backup(0)
  381. return
  382. }
  383. nr := l.next(1)
  384. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  385. l.backup(0)
  386. return
  387. }
  388. }
  389. r = l.next(0)
  390. }
  391. if r != RuneEOF {
  392. l.backup(0)
  393. }
  394. }
  395. /*
  396. lexNumberBlock lexes a block potentially containing a number.
  397. */
  398. func lexNumberBlock(l *lexer) {
  399. r := l.next(0)
  400. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  401. if !unicode.IsNumber(r) && r != '.' {
  402. if r == 'e' {
  403. l1 := l.next(1)
  404. l2 := l.next(2)
  405. if l1 != '+' || !unicode.IsNumber(l2) {
  406. break
  407. }
  408. l.next(0)
  409. l.next(0)
  410. } else {
  411. break
  412. }
  413. }
  414. r = l.next(0)
  415. }
  416. if r != RuneEOF {
  417. l.backup(0)
  418. }
  419. }
  420. // State functions
  421. // ===============
  422. /*
  423. lexToken is the main entry function for the lexer.
  424. */
  425. func lexToken(l *lexer) lexFunc {
  426. // Check if we got a quoted value or a comment
  427. n1 := l.next(1)
  428. n2 := l.next(2)
  429. // Parse comments
  430. if (n1 == '/' && n2 == '*') || n1 == '#' {
  431. return lexComment
  432. }
  433. // Parse strings
  434. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  435. return lexValue
  436. }
  437. // Lex a block of text and emit any found tokens
  438. l.startNew()
  439. // First try to parse a number
  440. lexNumberBlock(l)
  441. keywordCandidate := strings.ToLower(l.input[l.start:l.pos])
  442. // Check for number
  443. if numberPattern.MatchString(keywordCandidate) {
  444. _, err := strconv.ParseFloat(keywordCandidate, 64)
  445. if err == nil {
  446. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false)
  447. return lexToken
  448. }
  449. }
  450. if len(keywordCandidate) > 0 {
  451. l.backup(l.pos - l.start)
  452. }
  453. lexTextBlock(l, true)
  454. keywordCandidate = strings.ToLower(l.input[l.start:l.pos])
  455. // Check for keyword
  456. token, ok := KeywordMap[keywordCandidate]
  457. if !ok {
  458. // Check for symbol
  459. token, ok = SymbolMap[keywordCandidate]
  460. }
  461. if ok {
  462. // A known token was found
  463. l.emitToken(token)
  464. } else {
  465. if !namePattern.MatchString(keywordCandidate) {
  466. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  467. return nil
  468. }
  469. // An identifier was found
  470. l.emitTokenAndValue(TokenIDENTIFIER, keywordCandidate, true)
  471. }
  472. return lexToken
  473. }
  474. /*
  475. lexValue lexes a string value.
  476. Values can be declared in different ways:
  477. ' ... ' or " ... "
  478. Characters are parsed between quotes (escape sequences are interpreted)
  479. r' ... ' or r" ... "
  480. Characters are parsed plain between quote
  481. */
  482. func lexValue(l *lexer) lexFunc {
  483. var endToken rune
  484. l.startNew()
  485. allowEscapes := false
  486. r := l.next(0)
  487. // Check if we have a raw quoted string
  488. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  489. endToken = q
  490. l.next(0)
  491. } else {
  492. allowEscapes = true
  493. endToken = r
  494. }
  495. r = l.next(0)
  496. rprev := ' '
  497. lLine := l.line
  498. lLastnl := l.lastnl
  499. for (!allowEscapes && r != endToken) ||
  500. (allowEscapes && (r != endToken || rprev == '\\')) {
  501. if r == '\n' {
  502. lLine++
  503. lLastnl = l.pos
  504. }
  505. rprev = r
  506. r = l.next(0)
  507. if r == RuneEOF {
  508. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  509. return nil
  510. }
  511. }
  512. if allowEscapes {
  513. val := l.input[l.start+1 : l.pos-1]
  514. // Interpret escape sequences right away
  515. if endToken == '\'' {
  516. // Escape double quotes in a single quoted string
  517. val = strings.Replace(val, "\"", "\\\"", -1)
  518. }
  519. s, err := strconv.Unquote("\"" + val + "\"")
  520. if err != nil {
  521. l.emitError(err.Error() + " while parsing string")
  522. return nil
  523. }
  524. l.emitTokenAndValue(TokenSTRING, s, true)
  525. } else {
  526. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], true)
  527. }
  528. // Set newline
  529. l.line = lLine
  530. l.lastnl = lLastnl
  531. return lexToken
  532. }
  533. /*
  534. lexComment lexes comments.
  535. */
  536. func lexComment(l *lexer) lexFunc {
  537. // Consume initial /*
  538. r := l.next(0)
  539. if r == '#' {
  540. l.startNew()
  541. for r != '\n' && r != RuneEOF {
  542. r = l.next(0)
  543. }
  544. l.emitTokenAndValue(TokenPOSTCOMMENT, l.input[l.start:l.pos], false)
  545. if r == RuneEOF {
  546. return nil
  547. }
  548. l.line++
  549. } else {
  550. l.next(0)
  551. lLine := l.line
  552. lLastnl := l.lastnl
  553. l.startNew()
  554. r = l.next(0)
  555. for r != '*' && l.next(1) != '/' {
  556. if r == '\n' {
  557. lLine++
  558. lLastnl = l.pos
  559. }
  560. r = l.next(0)
  561. if r == RuneEOF {
  562. l.emitError("Unexpected end while reading comment")
  563. return nil
  564. }
  565. }
  566. l.emitTokenAndValue(TokenPRECOMMENT, l.input[l.start:l.pos-1], false)
  567. // Consume final /
  568. l.next(0)
  569. // Set newline
  570. l.line = lLine
  571. l.lastnl = lLastnl
  572. }
  573. return lexToken
  574. }